东华大学上海ACM全国邀请赛G题
Problem : Gem Squares
Description
You are given a board with 8×8 squares. In each square, there can be either a colored gem or no gem at all. Gems with different colors are represented by different integers. It is guaranteed that there are no more than two consecutive gems with the same color either in a row or in a column, and that there is not any gem above a blank square.
........
........
........
........
........
..43366.
..121556
44212335
For two neighboring squares, you can exchange the gems.
........
........
........
........
........
..43366.
..111556
44222335
If there are more than two consecutive gems with the same color in a row or in a column after exchange, these gems will be taken away simultaneously. Note that a gem could be counted both in its row and in its column; refer to the sample test cases for details.
........
........
........
........
........
..43366.
.....556
44...335
If there is no gem under a gem, the gem will fall to the square below.
........
........
........
........
........
.....66.
.....556
44433335
After all gems have fallen down to the lowest place, the procedure will be repeated. If there are more than two gems with the same color in a row or in a column, these gems will be taken away simultaneously. Then some gems will fall to the squares below, if there are no gems under those gems.
........
........
........
........
........
.....66.
.....556
.......5
........
........
........
........
........
........
.....666
.....555
........
........
........
........
........
........
........
........
The procedure will be repeated until there is no gem that can be taken away.
Given a board with 8*8 squares, you task is to determine whether all gems can be taken away by a single exchange or not.
Input
The input consists of several test cases. Each test case will be eight lines, and each line contains eight characters. If in a square there is no gem, ‘.’ is used to identify it, otherwise an integer k is used to identify the gem’s color, 1≤k≤9.
There is a blank line between two consecutive test cases.
End of input is indicated by a line consisting of 0.
Output
For each test case, output a single line. If all gems can be taken away by a single exchange, output “Yes”; otherwise output “No”.
CODE :
#include <iostream>
#include <cstring>
using namespace std;
typedef char Graph[8][9];
Graph operateMap,resMap;
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
int sameFlag[8][8];
char dot[9] = "........";
int x,y,cx,cy;
void copyMap(Graph a,Graph b); //图形拷贝函数
void outputMap(Graph g); //图形输出函数
bool searchMain(Graph g); //搜索的主体函数
void swap(char& a,char& b){char t = a;a = b;b = t; }; //交换函数
bool takeAway(Graph g); //检测是不是所有的数都可以TAKE AWAY
bool cmpMap(Graph g); //比较是不是全部都是'.'
bool sameNum(Graph g); //比较是不是有三连数
void delAndDown(Graph g); //消除，下落
int main()
{
freopen("data.txt","r",stdin);
int i,j,k;
while (scanf("%s",resMap[0])!=EOF)
{
if (resMap[0][0] == '0') break;
for (i=1;i<8;i++)
scanf("%s",resMap[i]);
copyMap(operateMap,resMap);
outputMap(operateMap);
//搜索的主体函数
if (searchMain(operateMap)) printf("Yes/n");
else printf("No/n");
getchar();
}
return 0;
}
void copyMap(Graph a,Graph b)
{
int i;
for (i=0;i<8;i++)
strcpy(a[i],b[i]);
}
void outputMap(Graph g)
{
int i;
printf("look at the map:/n");
for (i=0;i<8;i++)
printf("%s/n",g[i]);
printf("----------------/n");
}
bool searchMain(Graph g)
{
int i,j,k;
for (i=0;i<8;i++)
{
for (j=0;j<8;j++) //遍历所有的点
{
if (g[i][j] != '.') //如果是数字点
{
//那么向四个方向尝试交换
for (k=0;k<4;k++)
{
int tx = i + dir[k][0];
int ty = j + dir[k][1];
if (tx>=0 && tx<8 && ty>=0 && ty<8)
{
if (g[i][j] != g[tx][ty]) //如果不相同才交换
{
swap(g[i][j],g[tx][ty]); //交换
x=-1;y=-1;
if (g[i][j] == '.')
{x = i;y=j;cx=tx;cy=ty;}
// outputMap(operateMap);
if (takeAway(g))
{
return 1;
}
copyMap(operateMap,resMap);
}
}
}
}
}
}
return 0;
}
bool takeAway(Graph g)
{
memset(sameFlag,0,sizeof(sameFlag));
while (sameNum(g)) //检测相同数字的循环
{
//如果有检测到相同的数字，那么就都消除，下落
delAndDown(g);
if (cmpMap(g)) //如果全为'.'，就ALL TAKE AWAY
return 1;
memset(sameFlag,0,sizeof(sameFlag));
}
return 0;
}
void delAndDown(Graph g)
{
int i,j,k;
for (i=0;i<8;i++) //对于每一列
{
for (j=0;j<8;j++) //行从下住上找空
{
if (sameFlag[j][i])
{
//那么下落覆盖
for (k=j;k>0;k--)
{
g[k][i] = g[k-1][i];
}
g[0][i] = '.';
}
}
}
x = -1;y = -1;
}
bool cmpMap(Graph g)
{
int i;
for (i=0;i<8;i++)
{
if (strcmp(g[i],dot)) //如果有一个和dot不等 就是不等
{
return 0;
}
}
return 1;
}
bool sameNum(Graph g)
{
int i,j,cnt,k,t;
char cmp;
bool done=0;
//对于每一行，检测行三连
for (i=0;i<8;i++)
{
t = 0;
cmp = g[i][t];
cnt = 1;
for (j=1;j<8;j++)
{
if (cmp != g[i][j])
{
if (cnt >= 3)
{
done = 1;
for (k=t;k<j;k++)
{
sameFlag[i][k] = 1;
}
}
cnt = 1;
cmp = g[i][j];
t = j;
}
else
{
if (g[i][j] == '.') continue;
cnt++;
if (j == 7)
{
if (cnt >= 3)
{
done = 1;
for (k=t;k<=j;k++)
{
sameFlag[i][k] = 1;
}
}
}
}
}
}
//对于每一列，检测列三连
for (i=0;i<8;i++)
{
t = 0;
cmp = g[t][i];
cnt = 1;
for (j=1;j<8;j++)
{
if (cmp != g[j][i])
{
if (cnt >= 3)
{
done = 1;
for (k=t;k<j;k++)
{
sameFlag[k][i] = 1;
}
}
cnt = 1;
cmp = g[j][i];
t = j;
}
else
{
if (g[j][i] == '.') continue;
cnt++;
if (j == 7)
{
if (cnt >= 3)
{
done = 1;
for (k=t;k<=j;k++)
{
sameFlag[k][i] = 1;
}
}
}
}
}
}
//处理‘.’的情况
if(x!=-1) //如果X,Y是'.'那么要标记该点为1
{
sameFlag[x][y] = 1;
if (!done) //如果没有三数，那么悬空数可以下落
{
for (i=cx+1;i<8;i++)
{
if (g[i][cy] == '.')
sameFlag[i][cy] = 1;
}
done = 1;
}
}
//且如果不为DONE对应的交换点下方也要标记为1
// for(i=0;i<8;i++){ for (j=0;j<8;j++) printf("%d",sameFlag[i][j]);
// printf("/n");}
// outputMap(operateMap);
return done;
}