NEFUOJ-278-approach Angel

本文最后更新于:2021年6月5日 中午

本代码未能正确通过OJ,暂未解决,挖个坑待补

题目

Description

1
2
3
4
5
Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs, and GUARDs in the prison.

Angel's friends want to save Angel. Their task is: approach Angel. We assume that "approach Angel" is to get to the position where Angel stays. When there's a guard in the grid, we must kill him (or her?) to move into the grid. We assume that we moving up, down, right, left takes us 1 unit time, and killing a guard takes 1 unit time, too. And we are strong enough to kill all the guards.

You have to calculate the minimal time to approach Angel. (We can move only UP, DOWN, LEFT and RIGHT, to the neighbor grid within bound, of course.)

Input

1
2
3
4
5
First line contains two integers stand for N and M.

Then N lines follows, every line has M characters. "." stands for road, "a" stands for Angel, and "r" stands for each of Angel's friend.

Process to the end of the file.

Output

1
For each test case, your program should output a single integer, standing for the minimal time needed. If such a number does no exist, you should output a line containing "Poor ANGEL has to stay in the prison all his life." 

Sample Input

1
2
3
4
5
6
7
8
7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........

Sample Output

1
13

题目大意

大致就是要救一个公主,中间每走一格路就要消耗一次时间,杀一次守卫也要消耗一次时间,求最少要花费多少时间,如果救不了,就要输出

“Poor ANGEL has to stay in the prison all his life.”

理解

本题我目前想到的就是用dfs把每条路都走一遍,最后找出最短的时间消耗即可,在此过程中要注意dfs过程中对边界的控制

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N=210;

int mark[N][N];
char c[N][N];

int n,m,startx,starty,len,minl;

void dfs(int x, int y, int len)
{
if(x<0||x>=n||y<0||y>=m||mark[x][y]==1) return;//边界判定
if(len>=minl || c[x][y]=='#') return;//边界判定2
if(c[x][y]=='r')//到达终点
{
if(len<minl) minl=len;
return;
}
if(c[x][y]=='x') len++;//杀守卫
mark[x][y]=1;
dfs(x+1, y, len+1);//继续dfs
dfs(x-1,y,len+1);
dfs(x, y+1, len+1);
dfs(x, y-1, len+1);
mark[x][y]=0;//还原
}

int main()
{
while(cin>>n>>m)
{
memset(mark, 0, sizeof(mark));
for(int i=0;i<n;i++)
{
cin>>c[i];
for(int j=0;j<m;j++)
{
if(c[i][j]=='a')//找到了
{
startx=i; starty=j;
}
}
}
len=0;
minl=99999;
dfs(startx, starty, len);
if(minl<99999) cout<<minl<<endl;
else cout<<"Poor ANGEL has to stay in the prison all his life.";
}
return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!