TC SRM 593 DIV1 250(dfs)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

这图最多3色就可以搜2就行了

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<stdlib.h>

 #include<vector>

 #include<algorithm>

 #include<string>

 using namespace std;

 int vis[][],c[][],f[],mm;

 int dis[][] = {{,},{,},{-,},{,-},{-,},{,-}},n;

 int flag,m;

 int judge(int x,int y)

 {

     if(x<||y<||x>=n||y>=n)

     return ;

     return ;

 }

 int dfs(int x,int y,vector <string> board,int o)

 {

     int i;

     for(i =  ; i <  ; i++)

     {

         int tx = x+dis[i][];

         int ty = y+dis[i][];

         if(judge(tx,ty)&&board[tx][ty]=='X')

         {

             if(c[tx][ty])

             {

                 if(c[tx][ty]!=o)

                 return ;

             }

             else

             {

                 flag = ;

                 c[tx][ty] = o;

                 if(!dfs(tx,ty,board,-o))

                 return ;

             }

         }

     }

     return ;

 }

 class HexagonalBoard

 {

     public:

     int minColors(vector <string> board)

     {

         int i,j,k = board.size();

         n = k;

         int ff = ;

         for(i =  ; i < n ; i++)

         {

             for(j =  ; j < n ; j++)

             {

                 if(board[i][j]=='X'&&!c[i][j])

                 {

                     m++;

                     c[i][j] = ;

                     if(!dfs(i,j,board,-))

                     {

                         ff=;

                         break;

                     }

                 }

             }

             if(!ff) break;

         }

         if(!m) return ;

         if(!flag)

         return ;

         if(ff)

         return ;

         else

         return ;

     }

 };