Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

加油!!!!!DFS

Posted by IenhanceMa at 2017-02-18 13:14:30 on Problem 1979
//poj 1979
//


//DFS   模版


//对于有类似于地图的题型
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define mem0(a) memset(a,0,sizeof(a));
void dfs(int ,int);
const int Maxn = 25;
char map[Maxn][Maxn];

int d[4][2] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };

int n, m, t;
int ans;
int main()
{
	freopen("1.txt", "r", stdin);
	int sx, sy;
	while (scanf("%d%d%d", &n, &m) != EOF)
	{

		if (!n&&!m)
		{
			break;
		}
		mem0(map);
		ans = 0;
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				scanf("\n%c", &map[i][j]);
				if (map[i][j] == '@')
				{
					sx = i, sy = j;    //确定此时起始点的位置
					map[sx][sy] = '.';
				}
			}
			
		}

		dfs(sx,sy);

		printf("%d\n", ans);

	}


	return 0;
}


void dfs(int x, int y)
{
	//迭代写法
	map[x][y] = '#';
	ans++;
	for (int i = 0; i < 4; i++)
	{
		int nx = x + d[i][0];
		int ny = y + d[i][1];
		/*if (nx >= 0 && nx < m&&ny >= 0 && ny < n&&map[nx][ny] == '.')
		{
			dfs(nx, ny);
		}*/
		if (map[nx][ny] == '.')
		{
			dfs(nx, ny);
		}
	}
	return;



	//递归写法
	///*if (x>=0&&x<m&&y>=0&&y<n&&map[x][y] == '.')
	//{
	//	ans++;
	//	map[x][y] = '#';
	//}*/
	//if (map[x][y] == '.')
	//{
	//	ans++;
	//	map[x][y] = '#';
	//}
	//else
	//{
	//	return;
	//}
	//
	//dfs(x + 1, y);
	//dfs(x , y + 1);
	//dfs(x - 1, y);
	//dfs(x, y - 1);
	//return;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator