DFS
思路
从起点开始DFS,DFS函数中要先判断下标是否越界,如果不越界且当前元素为’.’或’@’再继续开始从4个方向分别DFS;
注意:每次DFS后都要把当前元素替换为’#’,避免走回头路(相当于标记数组);
只能用cin读入字符,因为如果用scanf的话,空格和回车也会读进去;
时间复杂度
C++ 代码
#include <iostream>
using namespace std;
const int maxn = 20;
int n, m;
char a[maxn][maxn];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void DFS(int x, int y, int& res){
if(x < 0 || x >= m || y < 0 || y >= n) return;
if(a[x][y] == '.' || a[x][y] == '@') {
res++;
a[x][y] = '#';//防止走回头路
for(int i = 0; i < 4; i ++) DFS(x + dx[i], y + dy[i], res);
}
}
int main(){
scanf("%d%d", &n, &m);
while(n && m){
int res = 0, start_x, start_y;
for(int i = 0; i < m; i ++){
for(int j = 0; j < n; j ++){
//scanf("%c", &a[i][j]);
cin >> a[i][j];
if(a[i][j] == '@') {start_x = i, start_y = j;}
}
}
DFS(start_x, start_y, res);
printf("%d\n", res);
scanf("%d%d", &n, &m);
}
return 0;
}