2014
03-23

# Beat drop

John recently found an interesting flash game on BBS. The game is mainly about making the best of the present waterdrops and use as little waterdrops as possible to eliminate all the
waterdrops on board.Now let’s briefly introduce the operations: The game board is a 6*6 square. At the beginning, there are waterdrops in some squares (in different sizes), gamers can obtain a larger waterdrop by adding little waterdrops to the square. When the number of little waterdrops in the square meets 4, the big waterdrop in the square breaks, producing 4 little waterdrops, in whatever circumstances, the broken waterdrop can only produce 4 little waterdrops, which then fly up, down left, right, four directions. When a little whatdrop meets a square that contains a waterdrop, it will be absorbed, and the one in the square will become larger, just the same as when you manually add one to the square. When multiple waterdrops arrive at （a square that contains a waterdrop） simultaneously, they will be absorbed by the square. If the waterdrop touch the edge of board, it disappears. Gamers hope to use the least waterdrops to eliminate the waterdrops on board, so they can make through more levels. For further details, please visit “flashempire”. John and other byr players are obsessed with the game, but he is just not good at it. It’s mainly because after he comes up with an order to add the waterdrop, he can’t imagine the layout. Now John needs your help. So you will be given a game board and how the waterdrops are distributed, and John will tell you how he is going to add the waterdrop, he hopes that you can tell him if it can make it through the level, if not, tell him what the board will be like at the end. We use a n*m square to represent the game board, and L to represent the up limit of the number of waterdrops each square can contain, the number of waterdrops in each square exceeds L, the drop breaks. And the broken water drop produces 4 little waterdrops that will fly in four directions in the same speed.

The first line will contain an integer T indicating the number of test cases For each test case, it starts with three integers n, m, L, where n is the number of the rows, m is the number of the columns, L is the up limit of the number each square can contain. 1<= n, m <= 100，5 <= L<=10. Then follows a n*m matrix indicating the initial state of the game board, you are assured that every element is non-negative and no larger than L. After the matrix, there will be a number q, indicating how John is going to add the waterdrop at the qth step. John only adds waterdrop when it is stabel after putting last waterdrop. So q line follows, each contains two integers x,y indicating the location John adds waterdrop. 1<=x<=n,1<=y<=m.

The first line will contain an integer T indicating the number of test cases For each test case, it starts with three integers n, m, L, where n is the number of the rows, m is the number of the columns, L is the up limit of the number each square can contain. 1<= n, m <= 100，5 <= L<=10. Then follows a n*m matrix indicating the initial state of the game board, you are assured that every element is non-negative and no larger than L. After the matrix, there will be a number q, indicating how John is going to add the waterdrop at the qth step. John only adds waterdrop when it is stabel after putting last waterdrop. So q line follows, each contains two integers x,y indicating the location John adds waterdrop. 1<=x<=n,1<=y<=m.

3
2 2 2
2 0
0 0
1
1 1
2 2 2
2 0
0 0
1
1 2
6 6 4
4 3 2 0 0 0
3 3 0 1 2 2
1 3 2 4 2 0
3 4 1 4 4 1
3 2 2 2 3 0
3 0 3 2 1 2
6
4 3
4 3
3 2
2 2
2 6
4 4

YES
NO
2 1
0 0
NO
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 4 4 

When multiple waterdrops arrive at （a square that contains a waterdrop） simultaneously, they will be absorbed by the square。

// Note:Your choice is C++ IDE   关键开始全为0，中间到达全为0，水滴同时到达则被同时吸收，矩阵行末多一空格
#include <iostream>
#include <queue>
using namespace std;
struct Cor_Node
{
long x,y,type,time;
};
long f[105][105],tag[105][105];
long dir[4][2]={1,0,0,1,-1,0,0,-1};
void BFS(long x,long y,long n,long m,long l)
{
Cor_Node tq,tcor;
queue<Cor_Node> q;
long i;
tq.x=x,tq.y=y,tq.type=-1,tq.time=1;
q.push(tq);
while(!q.empty())
{
tq=q.front(),q.pop();
if(tq.type==-1)
{
if(f[tq.x][tq.y]==l)
{
f[tq.x][tq.y]=0;
for(i=0;i<4;i++)
{
tcor.x=tq.x+dir[i][0],tcor.y=tq.y+dir[i][1];
tcor.type=i,tcor.time=tq.time+1;
if(tcor.x>=1&&tcor.x<=n&&tcor.y>=1&&tcor.y<=m)
q.push(tcor);
}
}
else
f[tq.x][tq.y]++;
continue;
}
if(f[tq.x][tq.y]==l)
{
f[tq.x][tq.y]=0;
tag[tq.x][tq.y]=tq.time;        //标记使水滴break时的时间
for(i=0;i<4;i++)
{
tcor.x=tq.x+dir[i][0],tcor.y=tq.y+dir[i][1];
tcor.type=i,tcor.time=tq.time+1;
if(tcor.x>=1&&tcor.x<=n&&tcor.y>=1&&tcor.y<=m)
q.push(tcor);
}
}
else if(f[tq.x][tq.y]!=0)
f[tq.x][tq.y]++;
else if(tag[tq.x][tq.y]!=tq.time)            //可能原来是0，也可能是之前处理过后为0，由tag标记，若处理后为0则同时到达的水滴则不处理（同时吸收），否则继续同一个方向前进
{
tq.x=tq.x+dir[tq.type][0],tq.y=tq.y+dir[tq.type][1];
tq.time++;
if(tq.x>=1&&tq.x<=n&&tq.y>=1&&tq.y<=m)
q.push(tq);
}
}
}
int main()
{
long l,i,j,q,test,x,y,n,m,flag;
//freopen("in.txt","r",stdin);
scanf("%ld",&test);
while(test–)
{
memset(tag,0,sizeof(tag));
scanf("%ld%ld%ld",&n,&m,&l);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%ld",&f[i][j]);
scanf("%ld",&q);
flag=1;
for(i=1;i<=n;i++)            //格局开始全为0？
{
for(j=1;j<=m;j++)
if(f[i][j]!=0)    break;
if(j<=m)    break;
}
if(i>n)
flag=0;
while(q–)
{
scanf("%ld%ld",&x,&y);
if(flag==1)                //一旦格局全为0，则不再处理
{
BFS(x,y,n,m,l);
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
if(f[i][j]!=0)    break;
if(j<=m)    break;
}
if(i>n)
flag=0;
}
}
if(flag==0)
printf("YES\n");
else
{
printf("NO\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
printf("%ld ",f[i][j]);        //行末多一个空格
putchar(‘\n’);
}
}
}
return 0;
} 参考：http://hi.baidu.com/liuzhi67/item/0375db2b9fbfa7c7ef10f166