红与黑
bfs 和 dfs python
from pythonds.basic.queue import Queue
def bfs(x, y):
q=Queue()
q.enqueue((x,y))
list1[x][y]='#'
num = 0
directions = [(-1,0), (0,1), (1,0), (0,-1)]
while not q.isEmpty():
t = q.dequeue()
num += 1
for i in range(4):
a, b = t[0] + directions[i][0], t[1] + directions[i][1]
if a < 0 or a >= m or b < 0 or b >= n or list1[a][b] != '.': continue
list1[a][b] = '#'
q.enqueue((a, b))
return num
def dfs(x, y):
list1[x][y]='#'
num = 1
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
for i in range(4):
a, b = x + directions[i][0], y + directions[i][1]
if a >= 0 and a < m and b >= 0 and b < n and list1[a][b] == '.':
num += dfs(a, b)
return num
if __name__=="__main__":
n, m = map(int, input().split())
while n or m:
list1 = []
for i in range(m):
list2 = list(input())
list1.append(list2)
for i in range(m):
for j in range(n):
if list1[i][j] == '@':
x, y = i, j
# print(bfs(x, y))
print(dfs(x, y))
n, m = map(int, input().split())
bfs c++
#include <iostream>
#include <queue>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 25;
int n, m;
char g[N][N];
int bfs(int sx, int sy)
{
queue<PII> q;
q.push({sx, sy});
g[sx][sy] = '#';
int res = 0;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
while (q.size())
{
auto t = q.front();
q.pop();
res ++ ;
for (int i = 0; i < 4; i ++ )
{
int x = t.x + dx[i], y = t.y + dy[i];
if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] != '.') continue;
g[x][y] = '#';
q.push({x, y});
}
}
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;
}
//by y总
dfs c++
#include <iostream>
using namespace std;
const int N = 25;
int n, m;
char g[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int dfs(int x, int y)
{
int res = 1;
g[x][y] = '#';
for (int i = 0; i < 4; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == '.')
res += dfs(a, b);
}
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;
}
//by y总