2014
03-06

# Gem Squares

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...12155644212335

For two neighboring squares, you can exchange the gems.

..........................................43366...11155644222335

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......55644...335

If there is no gem under a gem, the gem will fall to the square below.

.............................................66......55644433335

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.

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.

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.

........
........
........
........
........
..43366.
..121556
44212335

........
........
........
.2......
.2.22...
.1.11...
.2.22...
.2.22...

12121212
21212121
12121212
21212121
12121212
21212121
12121212
21212121

........
........
........
........
........
...96...
...96...
.996966.

0

Yes
Yes
No
Yes
Hint
You can also exchange a gem with a space in its neighbor.

For test case 2, all gems can be taken away by exchanging the leftmost “1” and the space on the right.


#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <map>
#include <vector>
#include <string>
using namespace std;
#define INF 0x3f3f3f3f
char maz[10][10];
int dirx[4]={0,1,0,-1};
int diry[4]={1,0,-1,0};
bool check(int x,int y)
{
return x>=1&&x<=8&&y>=1&&y<=8;
}
char tmp[10][10];
void down()
{
int p=8;
for(int i=1;i<=8;i++)
{
p=8;
while(tmp[p][i]!='.')
p--;
int n=p;
while(p>=1)
{
if(tmp[p][i]!='.')
{
tmp[n][i]=tmp[p][i];
tmp[p][i]='.';
n--;
}
p--;
}
}
}
int delt()
{
int cnt[4];
int amount=0;
int tx,ty;
bool visited[10][10];
memset(visited,0,sizeof visited);
for(int i=8;i>=1;i--)
{
for(int j=1;j<=8;j++)
{
cnt[0]=cnt[1]=cnt[2]=cnt[3]=0;
if(tmp[i][j]=='.'||visited[i][j]) continue;
for(int k=0;k<4;k++)
{
//cnt[k]=0;
int tx=i+dirx[k];
int ty=j+diry[k];
while(tmp[tx][ty]==tmp[i][j])
{
cnt[k]++;
tx=tx+dirx[k];
ty=ty+diry[k];
}
}
for(int m=0;m<2;m++)
{
if(cnt[m]+cnt[m+2]+1>=3)
{
tx=i+cnt[m]*dirx[m];ty=j+cnt[m]*diry[m];
for(int k=0;k<cnt[m]+cnt[m+2]+1;k++)
{
visited[tx][ty]=1;
tx+=dirx[m+2];
ty+=diry[m+2];
}
}
}
}
}
for(int i=1;i<=8;i++)
for(int j=1;j<=8;j++)
if(visited[i][j])
{
tmp[i][j]='.';
amount++;
}
if(amount) down();
return amount;
}
void outp()
{
for(int i=1;i<=8;i++)
{
for(int j=1;j<=8;j++)
cout<<tmp[i][j];
cout<<endl;
}

}
int main()
{
#ifdef Effca
freopen("1.in","r",stdin);
freopen("2.out","w",stdout);
#endif

while(scanf("%s",maz[1]+1))
{
if(maz[1][1]=='0') break;
int all=0;
for(int i=2;i<=8;i++)
scanf("%s",maz[i]+1);
for(int i=1;i<=8;i++)
for(int j=1;j<=8;j++)
if(maz[i][j]!='.') all++;
int cnt,pre;
bool flag=0;
for(int i=8;i>=1;i--)
{
if(flag) break;
for(int j=1;j<=8;j++)
{
if(flag) break;
for(int k=0;k<4;k++)
{
if(flag) break;
memcpy(tmp,maz,sizeof maz);
int tx=i+dirx[k];
int ty=j+diry[k];
cnt=0;pre=-1;
if(check(tx,ty)&&maz[i][j]!=maz[tx][ty])
{
swap(tmp[i][j],tmp[tx][ty]);
while(cnt!=pre&&cnt!=all)
{
pre=cnt;
cnt+=delt();

}
if(cnt==all) flag=1;
}
}
}
}
if(flag)
puts("Yes");
else
puts("No");
}

return 0;
}

1. 也不能说自己的观影品味已经被脑残粉qj了吧？脑残粉看他们自己的，关我什么事别人吃屎吃得很开心，我也不能说“我的饮食品味被qj了吧”