UVa572
第一次做DFS的题目，还一次AC了，开心1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
using namespace std;
char map[MAXN][MAXN];
int m,n;
int dir[8][2] = { { 0,-1 },{ 0,1 },{ 1,0 },{ -1,0 },{-1,-1},{-1,1},{1,-1},{1,1} };//因为题目意思是斜着也算连通，所以定义八个方向
void dfs(int si, int sj)
{
if (si<0 || si>m || sj<0 || sj>n)return;
for (int i = 0; i < 8; i++)
{
if (map[si + dir[i][0]][sj + dir[i][1]] == '@')
{
map[si + dir[i][0]][sj + dir[i][1]] ='*';//做过的地方就标记不能走
dfs(si + dir[i][0], sj + dir[i][1]);//递归把连通的地方都走一遍
}
}
return ;
}
int main()
{
while (cin >> m >> n&&n&&m)
{
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
cin >> map[i][j];
int num = 0; //记录连通分量
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (map[i][j] == '@') { dfs(i, j); num++; }
cout << num << endl;
}
}
这是最简单的DFS题目，我们老师和我们说DFS最精彩的地方应该是剪枝，因为DFS是要去走完整幅地图，效率还是很低的，要提高效率，就要适当剪枝，避免一些多余的步子，当然也不可过度剪枝，所以怎么剪枝还是要多想。