TC SRM 593 DIV1 250

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

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

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 #include <cmath>
 6 #include <algorithm>
 7 using namespace std;
 8 char p[51][51];
 9 int o[51][51];
10 int mp[2501][2501],pre[2501];
11 int a[6] = {0,0,1,-1,1,-1};
12 int b[6] = {1,-1,0,0,-1,1};
13 int num = 1;
14 int dfs(int x,int step)
15 {
16     int i;
17     for(i = 1;i < num;i ++)
18     {
19         if(i == x) continue;
20         if(mp[x][i]&&pre[x] == pre[i])
21         {
22             return 0;
23         }
24         else if(mp[x][i])
25         {
26             pre[i] = step%2 + 1;
27             if(dfs(i,step+1) == 0)
28             return 0;
29         }
30     }
31     return 1;
32 }
33 class HexagonalBoard
34 {
35     public :
36     int minColors(vector <string> board)
37     {
38         int i,j,k,n,flag;
39         n = board[0].size();
40         for(i = 0;i < n;i ++)
41         {
42             for(j = 0;j < n;j ++)
43             {
44                 if(board[i][j] == 'X')
45                 o[i][j] = num ++;
46             }
47         }
48         for(i = 0;i < n;i ++)
49         {
50             for(j = 0;j < n;j ++)
51             {
52                 if(board[i][j] != 'X') continue;
53                 if(flag == 0) flag = 1;
54                 for(k = 0;k < 6;k ++)
55                 {
56                     if(i + a[k] >= 0&&i + a[k] < n&&j + b[k] >= 0&&j + b[k] < n)
57                     {
58                         if(board[i+a[k]][j+b[k]] == 'X')
59                         {
60                             flag = 2;
61                             mp[o[i][j]][o[i+a[k]][j+b[k]]] = 1;
62                         }
63                     }
64                 }
65             }
66         }
67         if(flag == 2)
68         {
69             for(i = 1;i < num;i ++)
70             {
71                 if(!pre[i])
72                 {
73                     pre[i] = 2;
74                     if(dfs(i,0) == 0)
75                     return 3;
76                 }
77             }
78             return 2;
79         }
80         else if(flag == 1)
81         return 1;
82         else
83         return 0;
84     }
85 };