給定 n×m 网格(n,m ≤ 20),@ 為起點,. 為可通過,# 為障礙。求從起點出發能到達的格子數(含起點)。多組測試,以 0 0 結束。
標準四方向 DFS,訪問標記為 # 避免重複。邊界檢查:0 ≤ nx < n, 0 ≤ ny < m。
#include <iostream>
using namespace std;
int n, m, sx, sy, cnt;
char g[25][25];
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};
void dfs(int x, int y) {
cnt++;
g[x][y] = '#';
for (int i=0;i<4;i++) {
int nx=x+dx[i], ny=y+dy[i];
if (nx>=0 && nx=0 && ny>m>>n, n||m) {
cnt=0;
for (int i=0;i>g[i][j];
if (g[i][j]=='@') sx=i, sy=j;
}
dfs(sx,sy);
cout<
m(列),後 n(行)。char g[25][25],下標 [行][列]。vis 數組。O(n*m) 每測試用例,瞬間通過。
POJ 1979 是 DFS 連通區域計數的入門必刷題。掌握「四方向數組 + 邊界檢查 + 就地標記」的標準模板,可秒殺所有網格搜索基礎題。