「NOIP模拟赛」水灾

2014年6月1日4,0480

http://218.5.5.242:9018/JudgeOnline/problem.php?id=1452

题目描述

大雨应经下了几天雨，却还是没有停的样子。土豪CCY刚从外地赚完1e元回来，知道不久除了自己别墅，其他的地方都将会被洪水淹没。
CCY所在的城市可以用一个N*M(N,M<=50)的地图表示，地图上有五种符号：“. * X D S”。其中“X”表示石头，水和人都不能从上面经过。“.”表示平原，CCY和洪水都可以经过。“*”表示洪水开始地方（可能有多个地方开始发生洪水）。“D”表示CCY的别墅。“S”表示CCY现在的位置。
CCY每分钟可以向相邻位置移动，而洪水将会在CCY移动之后把相邻的没有的土地淹没（从已淹没的土地）。
求CCY回到别墅的最少时间。如果聪哥回不了家，就很可能会被淹死，那么他就要膜拜黄金大神涨RP来呼叫直升飞机，所以输出“ORZ hzwer!!!”。

输入

输入的第一行是两个整数N和M（N，M<=50）。
接下来是一个N行M列的字符矩阵，表示ccy所在城市的地图。

输出

输出仅有一个整数，为ccy回到别墅需要的最少时间。如果无解输出－1。

样例输入

3 3 D.* … .S.

样例输出

题解

先bfs出每个点被水淹没的时间，然后再次bfs

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#define inf 0x7fffffff
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();}
    return x*f;
}
int n,m,bx,by,ex,ey;
int t,w;
int xx[4]={1,-1,0,0},yy[4]={0,0,1,-1};
char ch[55];
bool mp[55][55];
int tim[55][55];
struct data{int x,y,step,f;}q[10005];
void bfs1()
{
     while(t!=w)
     {
         int x=q[t].x,y=q[t].y;t++;
         for(int i=0;i<4;i++)
         {
             int nowx=x+xx[i],nowy=y+yy[i];
             if(nowx>n||nowy>m||nowx<1||nowy<1||mp[nowx][nowy])continue;
             if((nowx==ex&&nowy==ey)||tim[nowx][nowy]!=inf)continue;
             tim[nowx][nowy]=tim[x][y]+1;
             q[w].x=nowx;q[w].y=nowy;w++;
         }
     }
}
void bfs2()
{
     t=0,w=1;q[0].x=bx;q[0].y=by;
     while(t!=w)
     {
               
         int x=q[t].x,y=q[t].y,step=q[t].step;t++;
         for(int i=0;i<4;i++)
         {
             int nowx=x+xx[i],nowy=y+yy[i];
             if(nowx>n||nowy>m||nowx<1||nowy<1||mp[nowx][nowy]||step+1>=tim[nowx][nowy])
                 continue;
             mp[nowx][nowy]=1;
             if(nowx==ex&&nowy==ey){printf("%d",step+1);return;}
             q[w].x=nowx;q[w].y=nowy;q[w].step=step+1;w++;
         }
     }
     printf("ORZ hzwer!!!");
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            tim[i][j]=inf;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",ch);
        for(int j=1;j<=m;j++)
        {
            if(ch[j-1]=='D'){ex=i;ey=j;}
            if(ch[j-1]=='S'){bx=i;by=j;}
            if(ch[j-1]=='X')mp[i][j]=1;
            if(ch[j-1]=='*'){q[w].x=i;q[w].y=j;tim[i][j]=0;w++;}
        }
    }
    bfs1();
    bfs2();
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<cstdlib>

#define inf 0x7fffffff

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();}

return x*f;

}

int n,m,bx,by,ex,ey;

int t,w;

int xx[4]={1,-1,0,0},yy[4]={0,0,1,-1};

char ch[55];

bool mp[55][55];

int tim[55][55];

struct data{int x,y,step,f;}q[10005];

void bfs1()

{

while(t!=w)

{

int x=q[t].x,y=q[t].y;t++;

for(int i=0;i<4;i++)

{

int nowx=x+xx[i],nowy=y+yy[i];

if(nowx>n||nowy>m||nowx<1||nowy<1||mp[nowx][nowy])continue;

if((nowx==ex&&nowy==ey)||tim[nowx][nowy]!=inf)continue;

tim[nowx][nowy]=tim[x][y]+1;

q[w].x=nowx;q[w].y=nowy;w++;

}

void bfs2()

{

t=0,w=1;q[0].x=bx;q[0].y=by;

while(t!=w)

{

int x=q[t].x,y=q[t].y,step=q[t].step;t++;

for(int i=0;i<4;i++)

{

int nowx=x+xx[i],nowy=y+yy[i];

if(nowx>n||nowy>m||nowx<1||nowy<1||mp[nowx][nowy]||step+1>=tim[nowx][nowy])

continue;

mp[nowx][nowy]=1;

if(nowx==ex&&nowy==ey){printf("%d",step+1);return;}

q[w].x=nowx;q[w].y=nowy;q[w].step=step+1;w++;

}

printf("ORZ hzwer!!!");

}

int main()

{

n=read(),m=read();

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

tim[i][j]=inf;

for(int i=1;i<=n;i++)

{

scanf("%s",ch);

for(int j=1;j<=m;j++)

{

if(ch[j-1]=='D'){ex=i;ey=j;}

if(ch[j-1]=='S'){bx=i;by=j;}

if(ch[j-1]=='X')mp[i][j]=1;

if(ch[j-1]=='*'){q[w].x=i;q[w].y=j;tim[i][j]=0;w++;}

}

bfs1();

bfs2();

return 0;

}

« 「BZOJ1627」[Usaco2007 Dec] 穿越泥地「NOIP模拟赛」密码锁 »

hzwer.com _ Home | http://hzwer.com

「NOIP模拟赛」水灾

题目描述

输入

输出

样例输入

样例输出

题解

分类目录

热门文章

Myfriends

近期评论