CodeForces - 510B(DFS 워터프루프)

 1 /*****************************************************************************************************************************************************************************************************
 2   :   N*M                           .
 3   :
 4        ,             4,  DFS            .
 5 *****************************************************************************************************************************************************************************************************/
 6 #include
 7 using namespace std;
 8 int m,n,b[105][105],book[105][105],du[300],vis[200];
 9 int temp[4][2]={{1,0},{-1,0},{0,-1},{0,1}},ok = 0;
10 inline void dfs(int x,int y,int fx,int fy,int color){
11     if (ok) return ;
12     for (int k = 0; k<4; ++k){
13         int u = x+temp[k][0]; int v = y+temp[k][1];
14         if (u<=0||v<=0||u>n||v>m||(u==fx&&v==fy)) continue;
15         if (b[u][v]==color){
16             if (book[u][v]==color){ ok=1; return;}
17             book[u][v] = color;
18             dfs(u,v,x,y,color);            
19         }
20     }
21 }
22 int main(){
23     cin>>n>>m; char c;
24     for (int i=1; i<=n; ++i)
25         for (int j=1; j<=m; ++j){
26             c = getchar();
27             while (c=='
'||c=='\r') c = getchar();
28             b[i][j] = c; du[c] ++;
29         }
30     for (int k=0; k<=200; ++k)
31         if (du[k]>=4){
32             ok = 0; memset(book,0,sizeof(book));
33             for (int i=1; i<=n; ++i)
34                 for (int j=1; j<=m; ++j)
35                 if (b[i][j]==k&&book[i][j]==0){
36                     book[i][j] = k; dfs(i,j,-1,-1,k); if (ok){ cout<<"Yes
"; return 0;}
37                 }
38         }
39     cout<<"No
";
40     return 0;
41 }