LETTers练习赛第十场 第四题

开始用深搜,写了大半突然发现不行,大牛指导下改用广搜,开始是单纯的广搜,只是对方向处理的时候有点特殊,即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,这道题输出矩阵时每行末会多一个空格。。。。

关键开始全为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;
}

原文地址:https://www.cnblogs.com/LETTers/p/2490569.html