https://www.acwing.com/problem/content/1115/
Flood Fill算法，对于格子问题，求连通块的最大数量
有两种写法，BFS和DFS
BFS
1 #include<iostream> 2 #include<queue> 3 #include<cstring> 4 using namespace std; 5 typedef pair<int,int> PII; 6 7 int n,m; 8 const int N=30; 9 char a[N][N]; 10 bool vis[N][N]; 11 12 int bfs(int sx,int sy){ 13 memset(vis,0,sizeof(vis)); 14 int res=0; 15 queue<PII> q; 16 int dx[]={-1,0,1,0},dy[]={0,1,0,-1}; 17 q.push({sx,sy}); 18 vis[sx][sy]=true; 19 while(q.size()){ 20 auto t=q.front(); 21 q.pop(); 22 res++; 23 int x=t.first,y=t.second; 24 for(int i=0;i<4;i++){ 25 int tx=x+dx[i],ty=y+dy[i]; 26 if(tx<0||tx>n||ty<0||ty>m||a[tx][ty]!='.'||vis[tx][ty]) continue; 27 vis[tx][ty]=1; 28 q.push({tx,ty}); 29 } 30 } 31 return res; 32 } 33 int main(void) 34 { 35 while(cin>>m>>n,m||n){ 36 int x,y; 37 for(int i=0;i<n;i++){ 38 for(int j=0;j<m;j++){ 39 cin>>a[i][j]; 40 if(a[i][j]=='@'){ 41 x=i,y=j; 42 } 43 } 44 } 45 cout<<bfs(x,y)<<endl; 46 } 47 return 0; 48 }
DFS
1 #include<iostream> 2 #include<queue> 3 #include<cstring> 4 using namespace std; 5 typedef pair<int,int> PII; 6 7 int n,m; 8 const int N=30; 9 char a[N][N]; 10 bool vis[N][N]; 11 int dx[]={-1,0,1,0},dy[]={0,1,0,-1}; 12 int dfs(int x,int y){ 13 int res=1; 14 vis[x][y]=1; 15 for(int i=0;i<4;i++){ 16 int tx=x+dx[i],ty=y+dy[i]; 17 if(tx>=0&&tx<n&&ty>=0&&ty<m&&a[tx][ty]=='.'&&!vis[tx][ty]){ 18 res+=dfs(tx,ty); 19 } 20 } 21 return res; 22 } 23 int main(void) 24 { 25 while(cin>>m>>n,m||n){ 26 memset(vis,0,sizeof(vis)); 27 int x,y; 28 for(int i=0;i<n;i++){ 29 for(int j=0;j<m;j++){ 30 cin>>a[i][j]; 31 if(a[i][j]=='@'){ 32 x=i,y=j; 33 } 34 } 35 } 36 cout<<dfs(x,y)<<endl; 37 } 38 return 0; 39 }