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;
}