仙岛求药

2019-08-24 作者:yzc216.com官网   |   浏览(126)

2727:仙岛求药,2727:仙岛

2727:仙岛求药

  • 查看
  • 提交
  • 统计
  • 提问

总时间限制:
1000ms

内存限制:
65536kB

描述
少年李逍遥的婶婶病了,王小虎介绍他去一趟仙灵岛,向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛,克服了千险万难来到岛的中心,发现仙药摆在了迷阵的深处。迷阵由M×N个方格组成,有的方格内有可以瞬秒李逍遥的怪物,而有的方格内则是安全。现在李逍遥想尽快找到仙药,显然他应避开有怪物的方格,并经过最少的方格,而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。
下图 显示了一个迷阵的样例及李逍遥找到仙药的路线.
图片 1

输入
输入有多组测试数据. 每组测试数据以两个非零整数 M 和 N 开始,两者均不大于20。M 表示迷阵行数, N 表示迷阵列数。接下来有 M 行, 每行包含N个字符,不同字符分别代表不同含义:
1) ‘@’:少年李逍遥所在的位置;
2) ‘.’:可以安全通行的方格;
3) ‘#’:有怪物的方格;
4) ‘*’:仙药所在位置。
当在一行中读入的是两个零时,表示输入结束。

输出
对于每组测试数据,分别输出一行,该行包含李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。如果他不可能找到仙药, 则输出 -1。

样例输入
8 8 .@##...#

#....#.#
#.#.##..
..#.###.
#.#...#.
..###.#.
...#.*..
.#...###
6 5
.*.#.
.#...
..##.
.....
.#...
....@
9 6
.#..#. 
.#.*.# 
.####. 
..#... 
..#... 
..#... 
..#... 
#.@.## 
.#..#. 
0 0

样例输出
10 8 -1

bfs裸题,注意每组数据之间的衔接

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 int bgx,bgy,edx,edy;
 7 const int MAXN=1001;
 8 int map[MAXN][MAXN];
 9 bool vis[MAXN][MAXN];
10 int xx[6]={-1, 1,0,0};
11 int yy[6]={0,0,-1, 1};
12 int n,m;
13 struct node
14 {
15     int x;
16     int y;
17     int step;
18 }cur,nxt;
19 queue<node>q;
20 void bfs(int x,int y)
21 {
22     while(q.size()!=0)q.pop();
23     cur.x=x;    cur.y=y;    cur.step=0;
24     q.push(cur);
25     vis[x][y]=1;
26     int flag=0;
27     while(q.size()!=0)
28     {
29         node p=q.front();
30         q.pop();
31         for(int i=0;i<4;i  )
32         {
33             int wx=p.x xx[i];
34             int wy=p.y yy[i];
35             if(wx>=1&&wx<=n&&wy>=1&&wy<=m&&vis[wx][wy]==0&&map[wx][wy]!=1)
36             {
37                 if(map[wx][wy]==2)
38                 {
39                     printf("%dn",p.step 1);
40                     flag=1;
41                     break;
42                 }
43                 else
44                 {
45                     nxt.x=wx;
46                     nxt.y=wy;
47                     nxt.step=p.step 1;
48                     q.push(nxt);
49                     vis[wx][wy]=1;
50                 }
51             }
52         }
53         if(flag==1)break;
54     }
55     if(flag==0)
56     printf("-1n");
57 }
58 int main()
59 {
60     while(scanf("%d%d",&n,&m))
61     {
62         memset(map,0,sizeof(map));
63         memset(vis,0,sizeof(vis));
64         if(n==0&&m==0)break;
65         for(int i=1;i<=n;i  )
66         {
67             for(int j=1;j<=m;j  )
68             {
69                 char c;
70                 cin>>c;
71                 if(c=='@')     {bgx=i;bgy=j;map[i][j]=1;}
72                 if(c=='*')    {edx=i;edy=j;map[i][j]=2;}
73                 if(c=='#')     {map[i][j]=1;}
74                 if(c=='.')     {map[i][j]=0;}
75             }
76         }
77         bfs(bgx,bgy);
78     }
79     return 0;
80 }

 

2727:仙岛求药

  • 查看
  • 提交
  • 统计
  • 提问

总时间限制:
1000ms

内存限制:
65536kB

描述
少年李逍遥的婶婶病了,王小虎介绍他去一趟仙灵岛,向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛,克服了千险万难来到岛的中心,发现仙药摆在了迷阵的深处。迷阵由M×N个方格组成,有的方格内有可以瞬秒李逍遥的怪物,而有的方格内则是安全。现在李逍遥想尽快找到仙药,显然他应避开有怪物的方格,并经过最少的方格,而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。
下图 显示了一个迷阵的样例及李逍遥找到仙药的路线.
图片 2

输入
输入有多组测试数据. 每组测试数据以两个非零整数 M 和 N 开始,两者均不大于20。M 表示迷阵行数, N 表示迷阵列数。接下来有 M 行, 每行包含N个字符,不同字符分别代表不同含义:
1) ‘@’:少年李逍遥所在的位置;
2) ‘.’:可以安全通行的方格;
3) ‘#’:有怪物的方格;
4) ‘*’:仙药所在位置。
当在一行中读入的是两个零时,表示输入结束。

输出
对于每组测试数据,分别输出一行,该行包含李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。如果他不可能找到仙药, 则输出 -1。

样例输入
8 8 [email protected]##...#

#....#.#
#.#.##..
..#.###.
#.#...#.
..###.#.
...#.*..
.#...###
6 5
.*.#.
.#...
..##.
.....
.#...
[email protected]
9 6
.#..#. 
.#.*.# 
.####. 
..#... 
..#... 
..#... 
..#... 
#[email protected]## 
.#..#. 
0 0

样例输出
10 8 -1

bfs裸题,注意每组数据之间的衔接

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 int bgx,bgy,edx,edy;
 7 const int MAXN=1001;
 8 int map[MAXN][MAXN];
 9 bool vis[MAXN][MAXN];
10 int xx[6]={-1, 1,0,0};
11 int yy[6]={0,0,-1, 1};
12 int n,m;
13 struct node
14 {
15     int x;
16     int y;
17     int step;
18 }cur,nxt;
19 queue<node>q;
20 void bfs(int x,int y)
21 {
22     while(q.size()!=0)q.pop();
23     cur.x=x;    cur.y=y;    cur.step=0;
24     q.push(cur);
25     vis[x][y]=1;
26     int flag=0;
27     while(q.size()!=0)
28     {
29         node p=q.front();
30         q.pop();
31         for(int i=0;i<4;i  )
32         {
33             int wx=p.x xx[i];
34             int wy=p.y yy[i];
35             if(wx>=1&&wx<=n&&wy>=1&&wy<=m&&vis[wx][wy]==0&&map[wx][wy]!=1)
36             {
37                 if(map[wx][wy]==2)
38                 {
39                     printf("%dn",p.step 1);
40                     flag=1;
41                     break;
42                 }
43                 else
44                 {
45                     nxt.x=wx;
46                     nxt.y=wy;
47                     nxt.step=p.step 1;
48                     q.push(nxt);
49                     vis[wx][wy]=1;
50                 }
51             }
52         }
53         if(flag==1)break;
54     }
55     if(flag==0)
56     printf("-1n");
57 }
58 int main()
59 {
60     while(scanf("%d%d",&n,&m))
61     {
62         memset(map,0,sizeof(map));
63         memset(vis,0,sizeof(vis));
64         if(n==0&&m==0)break;
65         for(int i=1;i<=n;i  )
66         {
67             for(int j=1;j<=m;j  )
68             {
69                 char c;
70                 cin>>c;
71                 if(c=='@')     {bgx=i;bgy=j;map[i][j]=1;}
72                 if(c=='*')    {edx=i;edy=j;map[i][j]=2;}
73                 if(c=='#')     {map[i][j]=1;}
74                 if(c=='.')     {map[i][j]=0;}
75             }
76         }
77         bfs(bgx,bgy);
78     }
79     return 0;
80 }

 

2727:仙岛求药 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB 描述 少年李逍遥的婶婶病了,王小虎介绍他...

本文由yzc216亚洲城发布于yzc216.com官网,转载请注明出处:仙岛求药

关键词: yzc216亚洲城 yzc216.com官网