12D:迷阵

总时间限制: 1000ms 内存限制: 65536kB描述

小Z每年都会为程设课出一道大作业,荼毒学弟学妹,可谓罪大恶极不可饶恕。

终于有一天,神明也看不下去了,他唤醒上古四大神兽,决定围困小Z,威慑一番。

于是,在小Z下一次醒来时,他便发现自己已然身处不知名的所在,抬眼所见,只有滚滚迷雾席卷而来,雾霭深处还隐隐约约闪着雷光。

低头一看,地上有一红漆木盒,上书四个大字“求生之道”,打开一看,竟是一台电脑。

电脑上空荡荡的,只有三个文件,一个是 Visual Studio 的安装包,一个是 README.txt,还有一个是 map.png。

小Z想都没想就开始安装 VS,在漫长的等待中,他打开了 README.txt:

“汝罪大恶极,故略施薄惩。此乃四象迷阵,有神兽镇守,踏错一步,险象环生。如欲得生,须观 map.png,寻得最短出路。”


迷阵是 m 行 n 列的格子矩阵,行、列从 1 开始数。小Z出生在左上角,也就是第 1 行,第 1 列的格子,迷阵的出口在第 m 行,第 n 列。

迷阵中有三种格子:

1. 空格子,以英文句点’.’记。出生点和出口都是空格子。
2. 墙,以井号’#’记。小Z无法移动到墙上。
3. 陷阱,以星号’*’记。小Z移动到陷阱的瞬间会受到来自上古神兽的 1 点伤害(生命 – 1),但是离开陷阱的瞬间不会再受到伤害。

小Z的生命有 H 点,当生命到 0 的瞬间他就会被传送回出生点。

小Z的每次行动是向上下左右的四个方向之一移动一格。不能移动出界,不能移动到墙上,但是可以移动到陷阱上。

小Z需要在短短3个小时内写出程序,算出自己最少要走多少步才能走到出口。

但凡迷阵,必有生门。题目保证必定存在一条路径使得小Z能够走到出口。

输入第一行是一个整数 T,表示输入包含 T 组数据,分别是不同的平行时空下小Z所处的迷阵。

对于每组数据,第一行包括三个整数:m(2 <= m <= 255)、n(2 <= n <= 255)、H(1 <= H <= 5)。

接下来 m 行,每行是一个由符号组成的长度为 n 的字符串,第 i 行的第 j 个字符表示矩阵中第 i 行第 j 列的格子的类型。

题目保证出生点和出口(左上角和右下角)都是空格子。输出对于每组数据,你需要输出一行一个正整数,表示小Z在这个迷阵中最少要走多少步才能走到出口。

题目保证小Z一定能走到出口。样例输入

2
2 2 3
.*
#.
5 5 3
.....
****.
.....
.****
.....

样例输出

2
8
 1 #include<iostream>
 2 #include<cstring>
 3 #include<queue>
 4 using namespace std;
 5 char a[260][260];
 6 bool visited[260][260][6];
 7 int dirx[4] = {0,0,1,-1};
 8 int diry[4] = {1,-1,0,0};
 9 int m, n, H;
10 struct node{
11     int x, y, step, h;
12     nodeint xx, int yy, int ss = 0, int hh = H):xxx),yyy),stepss),hhh){}
13 };
14 queue<node>q;
15 int main){
16     int t;
17     cin>>t;
18     whilet--){
19         cin>>m>>n>>H;
20         memseta, 0, sizeofa));
21         memsetvisited,0,sizeofvisited));
22         while!q.empty)) q.pop);
23         int i, j;
24         fori = 1; i <= m; i++)
25             forj = 1; j <= n; j++)
26                 cin>>a[i][j];
27         q.pushnode1,1));
28         visited[1][1][H] = true;
29         while!q.empty)){
30             node no = q.front);
31             q.pop);
32             int hp = no.h, step = no.step;
33             ifno.x==m&&no.y==n){
34                 cout<<no.step<<endl;
35                 break;
36             }
37             forint i = 0; i < 4; i++){
38                 int nx = no.x+dirx[i];
39                 int ny = no.y+diry[i];
40                 ifa[nx][ny]=='.'&&!visited[nx][ny][hp]){
41                     q.pushnodenx, ny,step+1, hp));
42                     visited[nx][ny][hp] = true;
43                 }
44                 ifa[nx][ny]=='*'&&hp-1>0&&!visited[nx][ny][hp-1]){
45                     q.pushnodenx, ny,step+1, hp-1));
46                     visited[nx][ny][hp-1] = true;
47                 }
48             }
49         }
50     }
51     return 0;
52 }

备注:这道题我WA了十次……对着AC代码也看不出来哪错了,查到怀疑人生。

结果就求助x老师了。然后老师就帮我找到了问题出在哪里,虽然他没有发现问题的本质。我居然还能把初始化列表写错! 把hhh)写成了hH)。我服了我自己了。

我太爱x老师了,希望他能明白我对他的爱。

Published by

风君子

独自遨游何稽首 揭天掀地慰生平

发表回复

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