3

.S.

.S.

大雨应经下了几天雨,却还是没有停的样子。土豪CCY刚从外地赚完1e元回来,知道不久除了自己别墅,其他的地方都将会被洪水淹没。

….S.

水灾(sliker.cpp/c/pas) 1000MS 
64MB

在bfs_2中,人每走一步之前,先bfs_1搜索洪水下一秒将要淹没点,然后搜索人走的路线。

输入文件 sliker.in

大雨应经下了几天雨,却还是没有停的样子。土豪CCY刚从外地赚完1e元回来,知道不久除了自己别墅,其他的地方都将会被洪水淹没。

.X.X..

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<queue>
 4 #include<cstring>
 5 #include<iostream>
 6 
 7 using namespace std;
 8 const int N = 110;
 9 
10 struct node{
11     int x,y,step;
12 }cur,nxt,t,u;
13 
14 queue <node> q;
15 queue <node> q2;
16 int mp[N][N];
17 bool v[N][N],v2[N][N];
18 int dx[5] = {0,1,0,-1};
19 int dy[5] = {1,0,-1,0};
20 int n,m,ex,ey,sx,sy,now;
21 char ch;
22 
23 void bfs_1(int w)    //搜出w+1秒的地图 
24 {
25     while(!q.empty())
26     {
27         cur = q.front();
28         if(cur.step!=w) return ;
29         q.pop();
30         for(int i=0;i<4;++i)
31         {
32             int a = dx[i]+cur.x;
33             int b = dy[i]+cur.y;
34             if(a>0 && b>0 && a<=n && b<=m && mp[a][b]==1 && !v[a][b])
35             {
36                 if(a==ex && b==ey) continue;
37                 mp[a][b] = 0;
38                 v[a][b] = true;
39                 nxt.x = a; nxt.y = b; nxt.step = cur.step+1;
40                 q.push(nxt);
41             }
42         }
43     }
44 }
45 void bfs_2()
46 {
47     now = 0;
48     bfs_1(now);
49     t.x = sx; t.y = sy; t.step = 0;
50     q2.push(t);
51     v2[sx][sy] = true;
52     while(!q2.empty())
53     {
54         t = q2.front();
55         if(t.step!=now) 
56         {now++; bfs_1(now); continue;}
57         q2.pop();
58         for(int i=0;i<4;++i)
59         {
60             int a = dx[i]+t.x;
61             int b = dy[i]+t.y;
62             if(a>0 && b>0 && a<=n && b<=m && mp[a][b]==1 && !v2[a][b])
63             {
64                 if(a==ex && b==ey)
65                 {
66                     printf("%d\n",t.step+1);return ;
67                 }
68                 v2[a][b] = true;
69                 u.x = a; u.y = b; u.step = t.step+1;
70                 q2.push(u);
71             }
72         }
73     }
74     printf("ORZ hzwer!!!\n");
75 }
76 int main()
77 {
78     freopen("sliker.in","r",stdin);
79     freopen("sliker.out","w",stdout);
80     scanf("%d%d",&n,&m);
81     for(int i=1;i<=n;++i)
82         for(int j=1;j<=m;++j)
83         {
84             cin>>ch;
85             if(ch=='S') sx=i,sy=j,mp[i][j]=1;
86             else if(ch=='D') ex=i,ey=j,mp[i][j]=1;
87             else if(ch=='*')
88             {
89                 mp[i][j] = 0;
90                 v[i][j] = true;
91                 cur.x = i; cur.y = j; cur.step = 0;
92                 q.push(cur); 
93             }
94             else if(ch=='.') mp[i][j] = 1;
95             else if(ch=='X') mp[i][j] = 3;
96         }
97     bfs_2();
98     return 0;    
99 }

 

 分析:找出洪水开始的所有节点,写两个广搜,另一个搜索洪水走的路线bfs_1,一个搜索人走的路线
bfs_2。

….S.

Input

ORZ hzwer!!!

输出文件 sliker.out

 

 

D…*.

求CCY回到别墅的最少时间。如果聪哥回不了家,就很可能会被淹死,那么他就要膜拜黄金大神涨RP来呼叫直升飞机,所以输出“ORZ
hzwer!!!”。

CCY所在的城市可以用一个N*M(N,M<=50)的地图表示,地图上有五种符号:“.
* X D
S”。其中“X”表示石头,水和人都不能从上面经过。“.”表示平原,CCY和洪水都可以经过。“*”表示洪水开始地方(可能有多个地方开始发生洪水)。“D”表示CCY的别墅。“S”表示CCY现在的位置。

D.*

 

Input

输出文件 sliker.out

CCY所在的城市可以用一个N*M(N,M<=50)的地图表示,地图上有五种符号:“.
* X D
S”。其中“X”表示石头,水和人都不能从上面经过。“.”表示平原,CCY和洪水都可以经过。“*”表示洪水开始地方(可能有多个地方开始发生洪水)。“D”表示CCY的别墅。“S”表示CCY现在的位置。

Input

3 6

Input

D…*.

3

Output

3 6

输入文件 sliker.in

 

D.*

..S

ORZ hzwer!!!

Output

Input

.X.X..

3 3

水灾(sliker.cpp/c/pas) 1000MS  64MB

CCY每分钟可以向相邻位置移动,而洪水将会在CCY移动之后把相邻的没有的土地淹没(从已淹没的土地)。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 using namespace std;
 6 int hx[60],hy[60],h;
 7 int x1,y1,x2,y2;
 8 int n,m;
 9 char c[60];
10 bool b[60][60],tx[51][51];
11 int tim[60][60],a[60][60];
12 int dx[]={1,0,-1,0};
13 int dy[]={0,1,0,-1};
14 int xx[2510],yy[2510];
15 void sousuo(int t,int x,int y)
16   {
17       tim[x][y]=min(t,tim[x][y]);
18       for(int i=0;i<4;i++)
19         {
20             int xx=x+dx[i],yy=y+dy[i];
21             if(b[xx][yy]&&xx>0&&xx<=n&&yy>0&&yy<=m&&t+1<tim[xx][yy])
22               sousuo(t+1,xx,yy);
23         }
24   }
25 int main()
26   {
27     freopen("sliker.in","r",stdin);
28      freopen("sliker.out","w",stdout);
29       scanf("%d%d",&n,&m);
30       for(int i=1;i<=n;i++)
31         {
32             cin>>c;
33             for(int j=0;j<m;j++)
34               {
35                   switch(c[j])// b数组标记能否走这个格子 
36                     {
37                         case '.':b[i][j+1]=true;break;
38                         case 'S':x1=i;y1=j+1;b[i][j+1]=true;break;
39                         case 'D':x2=i;y2=j+1;b[i][j+1]=false;break;// 别墅暂时标记为不能走 
40                         case '*':++h;hx[h]=i;hy[h]=j+1;break;// 记录洪水发生地点 
41                         case 'X':b[i][j+1]=false;break;
42                     }
43               }
44         }
45     memset(tim,127,sizeof(tim));// tim表示洪水到达该格点的最少时间 
46     memset(a,127,sizeof(a));// a表示人走到该格点的最少时间 
47       for(int i=1;i<=h;i++)
48         sousuo(0,hx[i],hy[i]);// 洪水所有的初始地点 
49       b[x2][y2]=true;// 将别墅 标记为能走 
50     xx[1]=x1,yy[1]=y1;
51     int head=0,tail=1;
52     a[x1][y1]=0;
53     tx[x1][y1]=true;// tx 数组标记是否已经走过 true为已经走过 
54     while(head<=tail)
55       {
56           ++head;
57           int x=xx[head],y=yy[head];
58           for(int i=0;i<4;i++)
59             {
60                 int mx=x+dx[i],my=y+dy[i];
61                 if(b[mx][my]==true&&mx>0&&mx<=n&&my>0&&my<=m&&a[x][y]+1<tim[mx][my])
62                   {// a[x][y]+1<tim[mx][my] 人能够在洪水到达该格子之前到达就说明可以走,否则-- 
63                       a[mx][my]=min(a[mx][my],a[x][y]+1);
64                       if(tx[mx][my]==false)
65                         {
66                             tx[mx][my]=true;
67                             tail++;
68                             xx[tail]=mx;
69                             yy[tail]=my;
70                   }
71               }
72             }
73       }
74       if(a[x2][y2]<a[0][0]) printf("%d\n",a[x2][y2]);
75       else                  printf("ORZ hzwer!!!\n");
76       fclose(stdin);fclose(stdout);
77       return 0;
78   }

Output

D.*

Output

Output

 

 

 

3 3

3 3

求CCY回到别墅的最少时间。如果聪哥回不了家,就很可能会被淹死,那么他就要膜拜黄金大神涨RP来呼叫直升飞机,所以输出“ORZ
hzwer!!!”。

Input

CCY每分钟可以向相邻位置移动,而洪水将会在CCY移动之后把相邻的没有的土地淹没(从已淹没的土地)。

3 3

6

 

 思路:见代码中解释

6

Output

..S

D.*

 

admin

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注