博客

迷宫问题II

Time Limit: 1000 MS Memory Limit: 32768 K Total Submit: 131 (42 users) Total Accepted: 44 (33 users) Rating: Special Judge: No

Description

小z身处在一个迷宫中，小z每分钟可以走到上下左右四个方向的相邻格之一。迷宫中有一些墙和障碍物。 同时迷宫中也有一些怪兽，当小z碰到任意一个怪兽时，小z需要将怪兽消灭掉才可以离开此方格。但消灭 怪兽会花费一定的时间。现在小z想知道走出迷宫需要花费的最少时间。

Input

输入第一行为组数T(T<=10)。 对于每组数据第一行为两个整数R和C(1<=R,C<=200)。以下R行每行有C个字符，即迷宫地图。 其中”#”代表墙和障碍物，”.”表示空地，[1~9]的数字代表此处有怪兽以及消灭此处的怪兽需要的时间. “Z”表示小z的起始位置，”W”表示迷宫出口。 对于每组数据保证起始位置和迷宫出口唯一。

Output

对于每组数据，输出走出迷宫的最短时间(单位:分钟)。如果无法走出迷宫则输出”IMPOSSIBLE”。

Sample Input

2 3 4 .Z.. .234 #.W. 4 4 Z.1. .32. ##4. W#..

Sample Output

5 IMPOSSIBLE

Hint

Author

#include<stdio.h>

#include<queue>

#include<string.h>

using namespace std;

struct zuobiao

{

int x,y,output;

friend bool operator <(zuobiao a,zuobiao b)

{

return a.output>b.output;

}

}now,nex;

char a[205][205];

int vis[205][205];

int fx[4]={0,0,1,-1};

int fy[4]={1,-1,0,0};

int n,m;

void bfs(int x,int y)

{

memset(vis,0,sizeof(vis));

priority_queue<zuobiao>s;

now.x=x;

now.y=y;

now.output=0;

s.push(now);

while(!s.empty())

{

now=s.top();

s.pop();

if(a[now.x][now.y]==’W’)

{

printf(“%d\n”,now.output);

return ;

}

for(int i=0;i<4;i++)

{

nex.x=now.x+fx[i];

nex.y=now.y+fy[i];

if(nex.x>=0&&nex.x<n&&nex.y>=0&&nex.y<m&&vis[nex.x][nex.y]==0&&a[nex.x][nex.y]!=’#’)

{

if(a[nex.x][nex.y]==’.’||a[nex.x][nex.y]==’W’)

nex.output=now.output+1;

if(a[nex.x][nex.y]>=’0’&&a[nex.x][nex.y]<=’9′)

nex.output=now.output+(a[nex.x][nex.y]-‘0’)+1;

vis[nex.x][nex.y]=1;

s.push(nex);

}

}

}

printf(“IMPOSSIBLE\n”);

return ;

}

int main()

{

int t;

scanf(“%d”,&t);

while(t–)

{

int x,y;

scanf(“%d%d”,&n,&m);

for(int i=0;i<n;i++)

{

scanf(“%s”,a[i]);

for(int j=0;j<m;j++)

{

if(a[i][j]==’Z’)

{

x=i;y=j;

}

}

}

bfs(x,y);

}

}