CSU 1726: 你经历过绝望吗？两次！ BFS,优先队列求解

Description

Input

Output

一个整数，为最少拆毁的障碍物数量,如果不能逃离废墟，输出-1。

Sample Input

3
3 3
###
#@*
***
3 4
####
#@.*
**.*
3 3
.#.
#@#
.#.

Sample Output

1
0
-1

Hint

Source

中南大学第十届大学生程序设计竞赛

Author

LVV

很明显的含有障碍物的迷宫问题，所以我们直接用优先队列做BFS直接就能求解了，优先队列中我们按照step步数设置优先级，'.'的代价为0，'\*'的代价为1，只要走到边界就输出对应的值

#include <iostream>
#include <cstring>
#include <stack>
#include <cstdio>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <set>
#include <map>const double eps=1e-8;
const double PI=acos(-1.0);
using namespace std;struct Node
{int x,y,step;friend bool operator <(Node a,Node b){return a.step>b.step;}
} node;int ans;
int c[][2]= {{1,0},{-1,0},{0,1},{0,-1}};
char a[105][105];
int n,m,a1,a2,n1,n2;
void bfs(int i,int j)
{//memset(vis,0,sizeof(vis));priority_queue<Node> q;node.x=i;node.y=j;node.step=0;a[i][j]='#';q.push(node);while(!q.empty()){Node temp,tp=q.top();q.pop();if(tp.x==n-1||tp.y==m-1||tp.x<=0||tp.y<=0){ans=tp.step;return ;}for(int k=0; k<4; k++){temp.x=tp.x+c[k][0];temp.y=tp.y+c[k][1];if(temp.x<n&&temp.y<m&&temp.x>=0&&temp.y>=0&&a[temp.x][temp.y]!='#'){if(a[temp.x][temp.y]=='*')temp.step=tp.step+1;elsetemp.step=tp.step;q.push(temp);a[temp.x][temp.y]='#';}}}ans=-1;
}int main()
{int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(int i=0; i<n; i++)//这里用字符串输入最好，用%c一个一个字符输入的时候OJ判WA，也不清楚为啥{scanf("%s",a[i]);}for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(a[i][j]=='@'){a1=i;a2=j;break;}}ans=0;bfs(a1,a2);printf("%d\n",ans);memset(a,0,sizeof(a));}return 0;
}