haut-1280 诡异的迷宫
2024-09-02 14:14:10
1280: 诡异的迷宫
时间限制: 2 秒 内存限制: 128 MB
提交: 174 解决: 27
提交 状态
题目描述
Simple最近刷题（打游戏）刷多了，一觉醒来发现自己到了一个迷宫里，怎么也出不去了。这时传来了一句话，告诉Simple必须按顺序收集完所有的宝石，才能出迷宫。所谓的顺序，就是按照每块宝石上英文字母的顺序。迷宫里面还有一些传送门，可以传送到任意一个另外的传送门的位置。（你走到一个不是空地上的地方的时候，就一定会触发相应事件，不可拒绝，从一个传送门传送到另一个传送门不用再次传送）。每走一步花费一个单位时间，传送门到另外一个传送门不需要时间。Simple初始就在字母为A的宝石的位置上（开局一宝石，其他全靠找）。
当Simple收集完所有宝石的时候就被传送出迷宫。
Simple还要赶回去刷题（打游戏），你们能告诉他最少需要多长时间才能回去吗？如果不可能出去就输出Impossible。
输入
多组实例，每组输入一个n，表示迷宫的大小为n*n (n <= 10)
下面n行每行n个字符
'.'表示空地，
'#'表示墙，不可以通过
'$'表示一个传送门
大写字母表示宝石
输出
每个实例输出一个数字，表示最少需要的时间，如果不能逃出迷宫，就输出Impossible。
样例输入
5
A....
####.
..B..
.####
C.DE. 2
AC
.B 2
A#
#B 3
A$.
...
.$B
样例输出
15
3
Impossible
2
/*
这题就是一个简单的bfs，只是要注意的地方有很多。
题目要求收集宝石只能按照英文字母的顺序，所以顺序不对的宝石当前是当作墙来看待的，是不能走的。
收集过的宝石的地方，是可以重复走的，不然有的时候就不能收集完所有宝石，所以每收集一次宝石，就相当于重新跑一次bfs
至于传送门，你踩到一个传送门，必须要传送到另一个传送门，此时到达另外一个传送门就不能触发效果了
*/
（我debug一个下午。。。）
附本人debug一下午的代码：
1 #include <cstdio>
2 #include <cmath>
3 #include <iostream>
4 #include <vector>
5 #include <set>
6 #include <sstream>
7 #include <algorithm>
8 #include <string>
9 #include <cstring>
10 using namespace std;
11 const int maxn = 15;
12 string st[maxn];
13 struct nod{
14 int x;
15 int y;
16 }tran[1050],nu[1050];
17 int vis[maxn][maxn];
18 int dir[5][2] = {{0,1},{1,0},{0,-1},{-1,0}};
19 int n;
20 int f = 0;
21 int sx,sy,len;
22 int cnt = 0,all = 0; //宝石
23 int head = 0,tail = 0;
24 void bfs(int sx,int sy) {
25 int xx,yy;
26 head = 0,tail = 1;
27 nu[head].x = sx;
28 nu[head].y = sy;
29 while(head != tail) {
30
31 int i;
32 for( i = 0; i < 4; i++) {
33 xx = nu[head].x + dir[i][0];
34 yy = nu[head].y + dir[i][1];
35 if(xx >= 0 && xx < n && yy >= 0 && yy < n && st[xx][yy] != '#' && !vis[xx][yy] ) {
36 if(st[xx][yy] == '.') {
37 nu[tail].x = xx;
38 nu[tail++].y = yy;
39 vis[xx][yy] = vis[nu[head].x][nu[head].y] + 1;
40
41 // cout<<vis[xx][yy]<<endl;
42 }
43 if(st[xx][yy] == '$') {
44
45 vis[xx][yy] = vis[nu[head].x][nu[head].y] + 1;
46 for(int j = 0; j < len; j++) {
47 if(!vis[tran[j].x][tran[j].y]) {
48
49
50 nu[tail].x = tran[j].x;
51 nu[tail++].y = tran[j].y;
52 vis[tran[j].x][tran[j].y] = vis[xx][yy];
53 // cout<< vis[tran[j].x][tran[j].y]<<endl;
54 continue;
55 }
56 }
57 }
58 else {
59 if(st[xx][yy] - 'A' == cnt + 1) {
60 // cout<<st[nu[head].x][nu[head].y]<<endl;
61 int u = vis[nu[head].x][nu[head].y] + 1;
62 nu[tail].x = xx;
63 nu[tail++].y = yy;
64 st[xx][yy] = '.';
65 head = tail - 1;
66 // cout<<xx<<yy<<"!!!"<<endl;
67 cnt++;
68 f = 1;
69
70
71 // cout<<"u "<<u<<endl;
72 memset(vis,0,sizeof(vis));
73 vis[nu[head].x][nu[head].y] = u;
74 // cout<<vis[nu[head].x][nu[head].y]<<"!!"<<endl;
75 // if(vis[nu[head].x][nu[head].y] == 5)
76
77 break;
78 // cout<<nu[head].x<<" "<<nu[head].y<<endl;
79 }
80
81 }
82 }
83 }
84 // cout<<i<<endl;
85 if(cnt == all) break;
86
87
88 if(f == 1) {
89 f = 0;
90 continue;
91 }
92 head++;
93 }
94 }
95 int main() {
96 ios::sync_with_stdio(false);
97
98 while(cin>>n) {
99 memset(vis,0,sizeof(vis));
100 cnt = 0,all = 0; //宝石
101 head = 0,tail = 0;
102 sx = 0,sy = 0,len = 0;
103 f = 0;
104 for(int i = 0; i < n; i++) {
105 cin>>st[i];
106 }
107
108
109 for(int i = 0; i < n; i++) {
110 for(int j = 0; j < n; j++) {
111
112 if(st[i][j] == 'A') {
113 st[i][j] = '.';
114 sx = i;
115 sy = j;
116 vis[i][j] = 1;
117 }
118 if(st[i][j] > 'A' && st[i][j] <= 'Z') all++;
119
120 if(st[i][j] == '$') {
121 tran[len].x = i;
122 tran[len++].y = j;
123 }
124 }
125
126 }
127 // cout<<all<<endl;
128 bfs(sx,sy);
129
130 if(cnt != all) cout<<"Impossible"<<endl;
131 else cout<<vis[nu[head].x][nu[head].y]-1<<endl;
132 }
133 return 0;
134 }
附标程：
1 #include<queue>
2 #include<cstdio>
3 #include<cstring>
4 #include<iostream>
5 #include<algorithm>
6
7 using namespace std;
8
9 struct door
10 {
11 int x,y;
12 }e[110];
13
14 int n,cnt,ce;
15 char a[15][15];
16 int b[15][15];
17 int dir[4][2] = {0,1,0,-1,1,0,-1,0};
18
19
20 struct node
21 {
22 int x,y,s,cnt;
23 };
24
25 void bfs(int x,int y)
26 {
27 memset(b,0,sizeof(b));
28 a[x][y] = '.';
29 b[x][y] = 1;
30 queue<node> q;
31 node t,next;
32 t.x = x;
33 t.y = y;
34 t.s = 0;
35 t.cnt = 1;
36 q.push(t);
37 while(!q.empty())
38 {
39 t = q.front();
40 q.pop();
41 if(t.cnt == cnt)
42 {
43 printf("%d\n",t.s);
44 return;
45 }
46 for(int i=0;i<4;i++)
47 {
48 int tx = t.x + dir[i][0];
49 int ty = t.y + dir[i][1];
50 if(tx < 0 || ty < 0 || tx >= n || ty >= n)
51 continue;
52 if(a[tx][ty] == '#' || b[tx][ty])
53 continue;
54 if(a[tx][ty] >= 'A' && a[tx][ty] <= 'Z' && a[tx][ty] != 'A' + t.cnt)
55 continue;
56 if(a[tx][ty] >= 'A' && a[tx][ty] <= 'Z')
57 {
58 next.x = tx;
59 next.y = ty;
60 next.s = t.s + 1;
61 next.cnt = t.cnt + 1;
62 a[tx][ty] = '.';
63 memset(b,0,sizeof(b));
64 while(!q.empty())
65 q.pop();
66 b[tx][ty] = 1;
67 q.push(next);
68 break;
69 }
70 if(a[tx][ty] == '$')
71 {
72 for(int j=0;j<ce;j++)
73 {
74 if(e[j].x == tx && e[j].y == ty)
75 continue;
76 if(b[e[j].x][e[j].y])
77 continue;
78 next.x = e[j].x;
79 next.y = e[j].y;
80 next.s = t.s + 1;
81 next.cnt = t.cnt;
82 b[e[j].x][e[j].y] = 1;
83 q.push(next);
84 continue;
85 }
86 continue;
87 }
88 next.x = tx;
89 next.y = ty;
90 next.s = t.s + 1;
91 next.cnt = t.cnt;
92 b[tx][ty] = 1;
93 q.push(next);
94 }
95 }
96 printf("Impossible\n");
97 }
98 int main(void)
99 {
100 int T,i,j,x,y;
101 while(scanf("%d",&n)==1)
102 {
103 cnt = 0;
104 ce = 0;
105 for(i=0;i<n;i++)
106 {
107 scanf("%s",a[i]);
108 for(j=0;j<n;j++)
109 {
110 if(a[i][j] == 'A')
111 x = i, y = j;
112 if(a[i][j] >= 'A' && a[i][j] <= 'Z')
113 cnt++;
114 if(a[i][j] == '$')
115 {
116 e[ce].x = i;
117 e[ce++].y = j;
118 }
119 }
120 }
121 bfs(x,y);
122 }
123
124 return 0;
125 }
最新文章
- ASP.NET Core 中文文档 第一章 入门
- Ubuntu14.10下安装JDK 8
- iOS集成ijkplayer视频直播框架，遇到的bug和坑...
- C语言中的字符和字符串
- 百度文库，linux下安装oracle客户端
- Windows Server 2003 激活码及激活方法
- 如何使用Json-lib
- （转）ubuntu下如何查看和设置分辨率
- Spring MVC 完整示例
- linux 定时执行任务
- stdcall、cdecl、fastcall、thiscall 、naked call的汇编详解
- 源码篇：SDWebImage
- Linuxc - 操作系统内存分配
- [转] fastText
- Babylon.js demo
- ES6_入门（2）_const命令
- 使用脚手架快速搭建React项目
- idHTTP 向网站发送json格式数据
- Centos6.8 Mysql5.6 安装配置教程(转)
- 黄聪：C#“多线程线程间操作无效: 从不是创建控件的线程访问它。”，跨线程修改控件属性解决方案