CSU oj 1726 你经历过绝望吗？两次！（bfs+优先队列求最短路）（搜索）

分手后的思念是犯贱 2022-08-21 12:39 16阅读 0赞

题目链接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1726

题目大意：给你一个矩阵，有路障栅栏和通路，通路可以直接走，路障不能走，栅栏可以走但需要拆除，问你最少拆除多少个栅栏能走到矩阵的最外围（即第一行最后一行或第一列或最后一列）。

解题思路：通常用bfs先走到的花费一定是最短的，但是这个不是，我们可以用优先队列来维护花费，这样就能保证先走到的花费一定是最短的。

#include <vector>
    #include <list>
    #include <map>
    #include <set>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <cstring>
    #include <ctime>
    #include <cassert>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    typedef long long LL;
     
    struct P
    {
        int x;
        int y;
        int val;
        P (int xx,int yy,int vall)
        {
            x=xx;
            y=yy;
            val=vall;
        }
    };
     
    struct cmp
    {
        bool operator()(P p1, P p2)
        {
            return p1.val>p2.val;
     
        }
     
    };
     
    int dx[4]= {-1,0,1,0};
    int dy[4]= {0,-1,0,1};
     
    int main()
    {
        int t;
        RI(t);
        while(t--)
        {
            char ttt[105][105];
            int maze[105][105];
            bool poi[105][105];
            int ans[105][105];
            int n,m;
            RII(n,m);
     
            for(int i=0; i<n; i++)
                    scanf("%s",ttt[i]);
     
            int sx,sy;
            for(int i=0; i<n; i++)
                for(int j=0; j<m; j++)
                {
                    if(ttt[i][j]=='#') maze[i][j]=3;
                    else if(ttt[i][j]=='*') maze[i][j]=2;
                    else if(ttt[i][j]=='.') maze[i][j]=1;
                    else
                    {
                        maze[i][j]=0;
                        sx=i;//hang
                        sy=j;//lie
                    }
                }
               // cout<<sx<<" "<<sy<<endl;
            priority_queue<P ,vector<P> ,cmp> pq;
     
            pq.push(P(sx,sy,0));
     
            mem(poi);
            for(int i=0; i<=100; i++)
                for(int j=0; j<=100; j++) ans[i][j]=inf;
            ans[sx][sy]=0;
            while(!pq.empty())
            {
                P p1=pq.top();
                pq.pop();
                for(int i=0; i<4; i++)
                {
                    int x=p1.x+dx[i];
                    int y=p1.y+dy[i];
                    if(x>=0&&x<n&&y>=0&&y<m&&maze[x][y]!=3&&!poi[x][y])
                    {
     
                        poi[x][y]=1;
                        if(maze[x][y]==1)    ans[x][y]=p1.val;
                        else if(maze[x][y]==2) ans[x][y]=p1.val+1;
                        pq.push(P(x,y,ans[x][y]));
                    }
                }
            }
            int anss=inf;
            for(int i=0;i<n;i++)
            {
                anss=min(anss,ans[i][0]);
                anss=min(anss,ans[i][m-1]);
            }
     
            for(int i=0;i<m;i++)
            {
                anss=min(anss,ans[0][i]);
                anss=min(anss,ans[n-1][i]);
            }
     
            printf("%d\n",anss==inf ? -1:anss);
        }
     
     
        return  0;
    }