USACO银牌题目 CF1365D Solve The Maze（DFS,Floodfill) 参考代码
#include <bits/stdc++.h>
using namespace std;
int maze[50][50];
void setblock(int i,int j,int n, int m){
maze[i][j]=1;
vector<pair<int,int>> nbv={{i,j-1},{i,j+1},{i-1,j},{i+1,j}};
for(auto k : nbv){
int x=k.first, y=k.second;
if(x>=0 && x<n && y>=0 && y<m){
maze[x][y]=1;
}
}
}
int DFS(int i,int j,int n, int m){
int reach_good=0;
stack<pair<int,int>> s;
bool vis[n][m];
memset(vis,false,sizeof(vis));
if(maze[i][j]==0){
s.push(make_pair(i,j));
vis[i][j]=true;
}
while(s.size()>0){
pair<int,int> a=s.top();
s.pop();
int i=a.first, j=a.second;
vector<pair<int,int>> nbv={{i,j-1},{i,j+1},{i-1,j},{i+1,j}};
for(auto k : nbv){
int x=k.first, y=k.second;
if(x>=0 && x<n && y>=0 && y<m){
if(!vis[x][y] && maze[x][y]!=1){
vis[x][y]=true;
s.push(make_pair(x,y));
if(maze[x][y]==2){//good person
reach_good++;
}
}
}
}
}
return reach_good;
}
int main()
{
int t;
cin>>t;
while(t>0){
t--;
int n,m;
cin>>n>>m;
int goodPersonCount=0;
memset(maze,0,sizeof(maze));
for(int i=0;i<n;i++){
string ts;
cin>>ts;
for(int j=0;j<m;j++){
if(ts[j]=='#'){
maze[i][j]=1;
}else{
if(ts[j]=='B'){
setblock(i,j,n,m);
}else{
if(ts[j]=='G'){
goodPersonCount++;
if(maze[i][j]==0){//not touched by bad guy
maze[i][j]=2;
}
}// for '.' do nothing
}
}
}
}
if(DFS(n-1,m-1,n,m) < goodPersonCount){
cout<<"No"<<endl;
}else{
cout<<"Yes"<<endl;
}
}
return 0;
}
