题目描述
有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。
你站在其中一块黑色的瓷砖上,只能向相邻(上下左右四个方向)的黑色瓷砖移动。
请写一个程序,计算你总共能够到达多少块黑色的瓷砖。
样例
输入样例:
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0
输出样例:
45
算法1
(宽搜) $O(nm)$
宽搜模板题。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
int n, m;
const int N = 25;
char g[N][N];
int bfs(int x, int y){
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, - 1};
queue<PII> q;
q.push({x, y});
int res = 1;
while (q.size()){
auto t = q.front(); q.pop();
for (int i = 0; i < 4; i ++){
int sx = t.x + dx[i], sy = t.y + dy[i];
if (sx >= 0 && sx < n && sy >= 0 && sy < m && g[sx][sy] == '.'){
q.push({sx, sy});
g[sx][sy] = '#';
res ++;
}
}
}
return res;
}
int main(){
while (cin >> m >> n, n || m){
for (int i = 0; i < n; i ++) cin >> g[i];
int x, y;
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
if (g[i][j] == '@') x = i, y = j;
cout << bfs(x, y) << endl;
}
return 0;
}
算法2
(深搜) $O(nm)$
注意dfs中res变量,是每次递归能搜索到的节点数。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
int n, m;
const int N = 25;
char g[N][N];
int dfs(int x, int y){
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
g[x][y] = '#';
int res = 1;//每一次dfs自己从自己本身的点开始计算,所以得重制res = 1。
for (int i = 0; i < 4; i ++){
int sx = x + dx[i], sy = y + dy[i];
if (sx >= 0 && sx < n && sy >= 0 && sy < m && g[sx][sy] == '.'){
res += dfs(sx, sy);
}
}
return res;
}
int main(){
while (cin >> m >> n, n || m){
for (int i = 0; i < n; i ++) cin >> g[i];
int x, y;
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
if (g[i][j] == '@') x = i, y = j;
cout << dfs(x, y) << endl;
}
return 0;
}