首页 > 搜索 > BFS搜索 > HDU 3451-Beat drop-BFS-[解题报告]HOJ
2014
03-23

HDU 3451-Beat drop-BFS-[解题报告]HOJ

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
Counting Sequences
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 

开始用深搜,写了大半突然发现不行,大牛指导下改用广搜,开始是单纯的广搜,只是对方向处理的时候有点特殊,即break出的小水滴若没遇到阻碍则一直沿相同方向前进,否则被吸收,如果吸收后的大水滴过了稳定的限制则重新break成四个方向的小水滴。WA

搜到一大牛博客,进一步发现如果在q次点击结束前已经到达了全为0的状态,则剩下的水滴不用再处理,输出YES,加上后依然WA 

然后放下,等自己灵感乍现吧

灵感乍现如果格局一开始就全为0,那就后面的点击都不用处理了,直接YES,WA 

要断网的时候又仔细看了遍题目,终于发现了关键点:

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

如果多个水滴同时到达一个有水滴存在的点,多个水滴将被同时吸收,并且最多也就break成四个小水滴向四个方向前进。。。

所以BFS里面还要加上小水滴到达每点的时间,如果多个小水滴同时到达,那么它们将被同时吸收,而不是只吸收使该点break的小水滴,多余的则会飞过,所有同时到达的水滴将被全部吸收!! 

觉得这就是关键了!

最后注意PE,这道题输出矩阵时每行末会多一个空格。。。。

// 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