zjuoj 3773 Paint the Grid

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3773

Paint the Grid

Time Limit: 2 Seconds Memory Limit: 65536 KB Special Judge

Leo has a grid with N × N cells. He wants to paint each cell either black or white.

After he finished painting, the grid will be divided into several parts. Any two connected cells should be in the same part, and any two unconnected cells should be in different parts. Two cells are connected if they share an edge and they are in the same color. If two cells are connected with the same another cell, the two cells are also connected.

The size of a part is the number of cells in it. Leo wants to have at least ⌊N×4÷3⌋ different sizes (⌊x⌋ is the maximum integer which is less than or equal to x).

Can you tell him how to paint the grid?

Input

There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For each test case:

There is one integer N (4 <= N <= 100).

Output

For each test case, output a solution to painting. You should output exactly N lines with each line contains N characters either 'X' (black) or 'O' (white). See the sample output for details.

This problem is special judged so any correct answer will be accepted.

Sample Input

1
5

Sample Output

XOXXX
OOOOO
XXXXX
OXXOO
OXXOO

Author: ZHOU, Yuchen
Source: The 14th Zhejiang University Programming Contest

分析：

给你一个染色的 N×M 的格子，你每次可以选择一个连通块，将其颜色取反。问最后将整个格子变为同色的最小步数。

思路：

其实就是一个最短路，将连通块缩点然后不同种的连通块之间连边，那么将整个格子变为同色的最小步数就等于一个点到地图上最远点的距离了。

AC代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <cmath>
  6 #include <string>
  7 #include <map>
  8 #include <stack>
  9 #include <vector>
 10 #include <set>
 11 #include <queue>
 12 #pragma comment (linker,"/STACK:1024000000,1024000000")
 13 #define maxn 45
 14 #define MAXN 2700005
 15 #define OO (1<<31)-1
 16 #define mod 1000000009
 17 #define INF 0x3f3f3f3f
 18 #define pi acos(-1.0)
 19 #define eps 1e-6
 20 typedef long long ll;
 21 using namespace std;
 22 
 23 int n,m,ans,cnt,lev;
 24 char mp[maxn][maxn];
 25 int num[maxn][maxn];
 26 int dx[]={0,0,-1,1};
 27 int dy[]={-1,1,0,0};
 28 
 29 bool vis[maxn][maxn],app[1605][1605];
 30 int p[1700];
 31 struct Node
 32 {
 33   int v;
 34   int next;
 35 }edge[MAXN];
 36 
 37 void addedge(int u,int v)
 38 {
 39   cnt++;
 40   edge[cnt].v=v;
 41   edge[cnt].next=p[u];
 42   p[u]=cnt;
 43 }
 44 bool isok(int x,int y)
 45 {
 46   if(x<1||x>n||y<1||y>m) return false ;
 47   return true ;
 48 }
 49 void dfs(int x,int y)
 50 {
 51   num[x][y]=lev;
 52   int nx,ny,i;
 53   for(i=0;i<4;i++)
 54   {
 55     nx=x+dx[i]; ny=y+dy[i];
 56     if(isok(nx,ny)&&!vis[nx][ny]&&mp[nx][ny]==mp[x][y])
 57     {
 58       vis[nx][ny]=1;
 59       dfs(nx,ny);
 60     }
 61   }
 62 }
 63 void presolve()
 64 {
 65   memset(p,0,sizeof(p));
 66   int i,j,k,t,nx,ny;
 67   lev=0;
 68   memset(vis,0,sizeof(vis));
 69   for(i=1;i<=n;i++)
 70   {
 71     for(j=1;j<=m;j++)
 72     {
 73       if(!vis[i][j])
 74       {
 75         lev++;
 76         vis[i][j]=1;
 77         dfs(i,j);
 78       }
 79     }
 80   }
 81   cnt=0;
 82   memset(app,0,sizeof(app));
 83   for(i=1;i<=n;i++)
 84   {
 85     for(j=1;j<=m;j++)
 86     {
 87       for(k=0;k<4;k++)
 88       {
 89         nx=i+dx[k]; ny=j+dy[k];
 90         if(isok(nx,ny)&&num[nx][ny]!=num[i][j]&&!app[num[nx][ny]][num[i][j]])
 91         {
 92           app[num[nx][ny]][num[i][j]]=1;
 93           addedge(num[nx][ny],num[i][j]);
 94         }
 95       }
 96     }
 97   }
 98 }
 99 struct fuck
100 {
101   int dis;
102   int num;
103 }t,f;
104 bool VVV[2700];
105 queue<fuck> Q;
106 int bfs(int now)
107 {
108   memset(VVV,0,sizeof(VVV));
109   t.dis=0;
110   t.num=now;
111   VVV[now]=1;
112   while(!Q.empty()) Q.pop();
113   Q.push(t);
114   int maxs=0;
115   while(!Q.empty())
116   {
117     t=Q.front();Q.pop();
118     if(t.dis>ans) return INF;
119     for(int i=p[t.num];i!=0;i=edge[i].next)
120     {
121       int to=edge[i].v;
122       if(!VVV[to])
123       {
124         VVV[to]=1;
125         f.num=to;
126         f.dis=t.dis+1;
127         maxs=max(maxs,f.dis);
128         Q.push(f);
129       }
130     }
131   }
132   return maxs;
133 }
134 int main()
135 {
136   int i,j,t,u,v,w;
137   scanf("%d",&t);
138   while(t--)
139   {
140     scanf("%d%d",&n,&m);
141     for(i=1;i<=n;i++)
142     {
143       scanf("%s",mp[i]+1);
144     }
145     presolve();
146     ans=INF;
147     for(int i=1;i<=lev;i++)
148     {
149       ans=min(ans,bfs(i));
150     }
151     printf("%d
",ans);
152   }
153   return 0;
154 }

View Code