TC SRM 593 DIV1 250

我只能说的亏没做，要不就挂0了。。

本来想四色定理，肯定4就可以的。。。然后准备爆，发现3的时候不好爆，又想了老一会，嗯，数据范围不小，应该不是暴力，直接找规律，貌似最大就是3，有一个3连块，输出3，其他输出2什么的。交，发现有环的时候，特殊的也是3。。。没办法还得暴力啊。暴力2的情况，写的也是各种错误。。。终于过了。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <vector>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 char p[][];

 int o[][];

 int mp[][],pre[];

 int a[] = {,,,-,,-};

 int b[] = {,-,,,-,};

 int num = ;

 int dfs(int x,int step)

 {

     int i;

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

     {

         if(i == x) continue;

         if(mp[x][i]&&pre[x] == pre[i])

         {

             return ;

         }

         else if(mp[x][i])

         {

             pre[i] = step% + ;

             if(dfs(i,step+) == )

             return ;

         }

     }

     return ;

 }

 class HexagonalBoard

 {

     public :

     int minColors(vector <string> board)

     {

         int i,j,k,n,flag;

         n = board[].size();

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

         {

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

             {

                 if(board[i][j] == 'X')

                 o[i][j] = num ++;

             }

         }

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

         {

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

             {

                 if(board[i][j] != 'X') continue;

                 if(flag == ) flag = ;

                 for(k = ;k < ;k ++)

                 {

                     if(i + a[k] >= &&i + a[k] < n&&j + b[k] >= &&j + b[k] < n)

                     {

                         if(board[i+a[k]][j+b[k]] == 'X')

                         {

                             flag = ;

                             mp[o[i][j]][o[i+a[k]][j+b[k]]] = ;

                         }

                     }

                 }

             }

         }

         if(flag == )

         {

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

             {

                 if(!pre[i])

                 {

                     pre[i] = ;

                     if(dfs(i,) == )

                     return ;

                 }

             }

             return ;

         }

         else if(flag == )

         return ;

         else

         return ;

     }

 };

巴特西

TC SRM 593 DIV1 250

最新文章

热门文章