C - 你经历过绝望吗？两次！【地图型BFS+优先队列（障碍物）】-白红宇

C - 你经历过绝望吗？两次！【地图型BFS+优先队列（障碍物）】

阅读量：6213 次

发布时间：2019-06-21

本文共 1870 字，大约阅读时间需要 6 分钟。

4月16日，日本熊本地区强震后，受灾严重的阿苏市一养猪场倒塌，幸运的是，猪圈里很多头猪依然坚强存活。当地15名消防员耗时一天解救围困的“猪坚强”。不过与在废墟中靠吃木炭饮雨水存活36天的中国汶川“猪坚强”相比，熊本的猪可没那么幸运，因为它们最终还是没能逃过被送往屠宰场的命运。

我们假设“猪坚强”被困在一个N*M的废墟中，其中“@”表示“猪坚强”的位置，“.”表示可以直接通过的空地，“#”表示不能拆毁的障碍物，“*”表示可以拆毁的障碍物，那么请问消防员至少要拆毁多少个障碍物，才能从废墟中救出“猪坚强”送往屠宰场？（当“猪坚强”通过空地或被拆毁的障碍物移动到废墟边缘时，视作被救出废墟）

Input

多组数据，第一行有一个整数T，表示有T组数据。（T<=100）

以下每组数据第一行有两个整数N和M。(1<=N,M<=100)

接着N行，每行有一个长度为M的字符串。

Output

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

Sample Input

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

Sample Output

10-1

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  #include
                   
                    #define ll long long#define inf 0x3fffffffusing namespace std;const int maxn = 105;struct Node{ int x,y,step; friend bool operator <(Node a,Node b) { return a.step>b.step; }};priority_queue
                    
                      q;int n,m;char a[maxn][maxn];//是char类型！！！int vis[maxn][maxn];int d[][2]={ { 1,0},{-1,0},{ 0,-1},{ 0,1}};int ans;bool check(int x,int y){ if(x<0 || x>=n || y<0 || y>=m || vis[x][y] || a[x][y]=='#')//“#”表示不能拆毁的障碍物！！！ return false; return true;}int bfs(int x1,int y1){ int ans=-1; while(!q.empty()) q.pop(); vis[x1][y1]=1; q.push( (Node){x1,y1,0} ); while(!q.empty()) { Node u=q.top(); q.pop(); if(u.x==0||u.x==n-1||u.y==0||u.y==m-1)//到达目标 //当“猪坚强”通过空地或被拆毁的障碍物移动到废墟边缘时，视作被救出废墟 { ans=u.step; break; } for(int i=0;i<4;i++)//遍历4个方向 { int x=u.x+d[i][0]; int y=u.y+d[i][1]; if(check(x,y))//检查边界 { // vis[x][y]=1; if(a[x][y]=='.')//“.”表示可以直接通过的空地，“*”表示可以拆毁的障碍物 q.push(Node{x,y,u.step});//遇到空地不用付出步数 else q.push(Node{x,y,u.step+1}); vis[x][y]=1; } } } return ans;//如果不能逃离废墟，输出-1 return x}int main(){ int t; scanf("%d",&t); int x1,y1,x2,y2; while(t--) { scanf("%d%d%",&n,&m); for(int i=0;i

转载于:https://www.cnblogs.com/Roni-i/p/7405232.html

你可能感兴趣的文章