P4554 小明的游戏 题解

· · 题解

写在前面

看了所有题解，都是用最短路或双端队列的 bfs，于是就有了本文：用了优先队列的 bfs。感觉和这题很像，但本题更容易。

算法分析

题目大意

给出一个 n \times m 的矩阵，问从起点（x_1,y_1）走到终点（x_2,y_2）的最少花费是多少？只能向上下左右四个方向移动，定义在两个不同类型的格子之间移动需要花费 1。

思路

看到这题第一反应就是用 bfs，但是直接 bfs 是错误的，因为最先到达终点的路线不一定最优。举个例子就懂了（下面用 0 表示 @，1 表示 #）：

0 1 0
0 1 0
0 0 0

起点为 0,0，终点为 0,2。那最先到达终点的路线为 0,0 \to 0,1 \to 0,2，花费 2。但是最优路线应该是 0,0 \to 1,0 \to 2,0 \to 2,1 \to 2,2 \to 1,2 \to 0,2，花费 0。

这里我们可以用贪心策略：每次从队列中取出新的点时，选择最小的那一个，并将这个点标记一下（不重复走），同时使用堆优化（这里有点像 dijkstra）。把普通队列改为优先队列，以走到当前这一格的花费进行排序，花费少的排在前面，这样就可以优先搜索花费更少的格子。

为什么这样做是对的？
因为花费不可能减少，所以每次新生成的点中花费最少的一定是当前的最优，那么以这个点向外扩散所产生的点应最优，以此类推，那么按这样搜索第一个到达终点的路线一定最优。

代码参考

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=510;
int n,m;
bool a[N][N];       //存矩阵：@ 为 1，# 为 0 
bool vis[N][N];     //标记数组 
int d[4][2]={1,0,-1,0,0,1,0,-1};
struct node{
    int x,y;        //当前格子的位置 
    int val;        //走到当前格子的花费 
};
bool operator <(const node &a,const node &b){   //花费小的排在前面 
    return a.val>b.val;
}
int bfs(int h1,int l1,int h2,int l2){
    priority_queue<node> q;
    vis[h1][l1]=1;
    q.push({h1,l1,0});
    while(!q.empty()){
        node t=q.top();
        int x=t.x, y=t.y, val=t.val;
        if(x==h2&&y==l2) return val; 
        q.pop();
        for(int i=0;i<4;++i){
            int xx=x+d[i][0];
            int yy=y+d[i][1];
            if(xx<0||xx>=n||yy<0||yy>=m) continue;      //判断边界 
            if(vis[xx][yy]) continue;
            vis[xx][yy]=1;
            if(a[x][y]==a[xx][yy])
                q.push({xx,yy,val});
            else 
                q.push({xx,yy,val+1});
        }
    }
}
signed main(){
    while(cin>>n&&cin>>m){
        if(n==0&&m==0) break;
        memset(a,0,sizeof a);       //一定要重置数组 
        memset(vis,0,sizeof vis);
        for(int i=0;i<n;++i)        //注意：从 0 开始 
            for(int j=0;j<m;++j){
                char x; cin>>x;
                if(x=='@') a[i][j]=1; 
            }
        int x,y,h,l;
        cin>>x>>y>>h>>l;
        cout<<bfs(x,y,h,l)<<endl;
    }

    return 0;
}