2014
03-16

# XieGang and FanXieGang

As we know, ‘/’ in chinese is “Xie Gang”, and ‘\’ is “Fan Xie Gang”, we can use them to build a beautiful labyrinth, for example :

here ‘/’ and ‘\’ in the labyrinth means walls, the wall which can’t separate two rooms we call it “inner wall”, for example, in he figure below, there are three “inner wall”s.

There are no more than 20000 cases. each case contains two integers n and m（n,m<=500）, the width and the height of the labyrinth, The next m lines represent the labyrinth itself, and contain n characters each, all these characters will be "/" or "\".

There are no more than 20000 cases. each case contains two integers n and m（n,m<=500）, the width and the height of the labyrinth, The next m lines represent the labyrinth itself, and contain n characters each, all these characters will be "/" or "\".

3 3
\/\
/\\
/\/
4 4
////
\\\\
////
\\\\

2
0

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define max 510
int mo[4][2]={ {-1,0}, {0,1}, {1,0}, {0,-1} };
struct node{
int ge[4];
int vis[4];
int fuhao;
}map[max][max];
struct data{           //每个1/4区域 map[x][y]的第g块
int x,y,g;
}d[max][max][4];
int m,n,color,white;
void bfs(int x,int y,int r)      //染色
{
queue <data> q;
int i,j,k;
if(map[x][y].vis[r])
return;
data t;
t.x=x;t.y=y;t.g=r;
q.push(t);
map[x][y].vis[r]=1;
map[x][y].ge[r]=color;
while(!q.empty())
{
data p;
p=q.front();
q.pop();
i=p.x;
j=p.y;
k=p.g;
if(map[i][j].fuhao=='\\')
{
if(map[i][j].vis[(5-k)%4]==0)  //本格
{
q.push(d[i][j][(5-k)%4]);
map[i][j].vis[(5-k)%4]=1;
map[i][j].ge[(5-k)%4]=color;
}
if(0<=i+mo[k][0]&&i+mo[k][0]<m && 0<=j+mo[k][1]&&j+mo[k][1]<n)
{
if(map[i+mo[k][0]][j+mo[k][1]].vis[(k+2)%4]==0)
{
map[i+mo[k][0]][j+mo[k][1]].vis[(k+2)%4]=1;
map[i+mo[k][0]][j+mo[k][1]].ge[(k+2)%4]=color;
q.push(d[i+mo[k][0]][j+mo[k][1]][(k+2)%4]);
}
}
}
else
{
if(map[i][j].vis[3-k]==0)  //本格
{
q.push(d[i][j][3-k]);
map[i][j].vis[3-k]=1;
map[i][j].ge[3-k]=color;
}
if(0<=i+mo[k][0]&&i+mo[k][0]<m && 0<=j+mo[k][1]&&j+mo[k][1]<n)
{
if(map[i+mo[k][0]][j+mo[k][1]].vis[(k+2)%4]==0)
{
map[i+mo[k][0]][j+mo[k][1]].vis[(k+2)%4]=1;
map[i+mo[k][0]][j+mo[k][1]].ge[(k+2)%4]=color;
q.push(d[i+mo[k][0]][j+mo[k][1]][(k+2)%4]);
}
}
}
}
}
void init()
{
int i,j,k;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
for(k=0;k<4;k++)
{
map[i][j].vis[k]=0;
map[i][j].fuhao=0;
map[i][j].ge[k]=0;
}
}
}
int main()
{
int i,j,k;
while(scanf("%d %d",&n,&m)!=EOF)
{
getchar();
//memset(map,0,sizeof(map));  //会超时
init();
color=0;
white=0;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
scanf("%c",&map[i][j].fuhao);
for(k=0;k<4;k++)
{
d[i][j][k].x=i;
d[i][j][k].y=j;
d[i][j][k].g=k;
}
}

getchar();
}
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
for(k=0;k<4;k++)
{
if(map[i][j].vis[k]==0)
{
color++;
bfs(i,j,k);
}
}
}
}
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
int flag=0,t=map[i][j].ge[0];
for(k=1;k<4;k++)
{
if(t!=map[i][j].ge[k])
{
flag=1;
break;
}
}
if(!flag)
white++;
}
}
printf("%d\n",white);
}
return 0;
}

, ,
1. 一开始就规定不相邻节点颜色相同，可能得不到最优解。我想个类似的算法，也不确定是否总能得到最优解：先着一个点，随机挑一个相邻点，着第二色，继续随机选一个点，但必须至少有一个边和已着点相邻，着上不同色，当然尽量不增加新色，直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢