临沧市建设局网站,制作小公司网站一般多少钱,哪个网站推广好,网址大全分类之一览表大全网题干#xff1a;
小z身处在一个迷宫中#xff0c;小z每分钟可以走到上下左右四个方向的相邻格之一。迷宫中有一些墙和障碍物。 同时迷宫中也有一些怪兽#xff0c;当小z碰到任意一个怪兽时#xff0c;小z需要将怪兽消灭掉才可以离开此方格。但消灭 怪兽会花费一定的时间。…题干
小z身处在一个迷宫中小z每分钟可以走到上下左右四个方向的相邻格之一。迷宫中有一些墙和障碍物。 同时迷宫中也有一些怪兽当小z碰到任意一个怪兽时小z需要将怪兽消灭掉才可以离开此方格。但消灭 怪兽会花费一定的时间。现在小z想知道走出迷宫需要花费的最少时间。
Input
输入第一行为组数T(T10)。
对于每组数据第一行为两个整数R和C(1R,C200)。以下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
解题报告 优先队列搞一波pq如果是普通的bfs那么队列即可因为队列就能保证取出来的Node结构体的t是最小值但是这题不一样所以需要pq。刚开始写的时候wa了好几发最后发现是main函数中那个双层循环的内层循环写成了for(int ji; jm; j)、、、我也是醉了好像不止第一次错在这里了、、、
AC代码
#includecstdio
#includequeue
#includecstring
#includecmath
#includemap
#includeiostream
#includealgorithm
#define ll long long
using namespace std;
struct Node {int x,y;int t;Node(){}Node(int x,int y,int t):x(x),y(y),t(t){} bool operator(const Node b) const{return t b.t;}
};
int n,m;
int nx[4]{0,1,0,-1};
int ny[4]{1,0,-1,0};
bool vis[205][205];
char maze[205][205];
int bfs(int sx,int sy) {priority_queueNode pq;pq.push(Node(sx,sy,0));Node cur;int tx,ty;while(pq.size()) {curpq.top();pq.pop(); for(int k 0; k4; k) {tx cur.x nx[k];ty cur.y ny[k];if(maze[tx][ty] # || vis[tx][ty] || tx 1 || tx n || ty 1 || ty m) continue;vis[tx][ty]1;if(maze[tx][ty] W) return cur.t 1;else if(maze[tx][ty] .) pq.push(Node(tx,ty,cur.t1));else pq.push(Node(tx,ty,cur.t 1 maze[tx][ty] - 0));}}return -1;}
int main()
{int t,sx,sy;cint;while(t--) {scanf(%d%d,n,m);memset(vis,0,sizeof vis);for(int i 1; in; i) {scanf(%s,maze[i]1);}for(int i 1; in; i) {for(int j 1; jm; j) {if(maze[i][j] Z) {sxi,syj;break;}}}int ans bfs(sx,sy);if(ans -1) puts(IMPOSSIBLE);else printf(%d\n,ans);}return 0 ;
}
