| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
加油!!!!!DFS//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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator