【牛客小白75】D 矩阵 【bfs+优先队列】

题目

https://ac.nowcoder.com/acm/contest/60063/D

题意是说，给你一张 \(n * m(n,m \leq 10^3)\) 大小的01地图，当前点下一步只能走到相邻的点上，如果这两个点值相同，则代价为2，否则代价为1，问从（1，1）走到（n，m）最少代价是多少

思路

首先很容易想到只往右下走是错的，有可能往左和往上走总代价更小

那么状态转移就不能两层循环解决了，有点类似dp，但是实现需要用到bfs，bfs的依据是从当前代价最小的状态的点开始往其他地方转移，因此使用优先队列

具体来说，因为从第一个点开始走的路径上的值一定是010101...或者101010....，所以先根据从起点开始走到的奇数or偶数步给每个点一个初始的cost，再把他们修改为相应的0或1；

bfs的时候如果当前的代价大于这个点的最小代价，就continue掉

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1000 + 10;
ll dp[N][N], a[N][N], add[N][N];
bool vis[N][N];
int n, m;
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
struct node{
    int x;
    int y;
    ll t;
    bool operator < (const node &aa) const {
        return t > aa.t;   
    }
};

void solve() {
    memset(dp, 0x3f3f3f3f, sizeof(dp));
    dp[1][1] = 0;
    priority_queue<node> q;
    q.push((node){1, 1, 0});
    while(!q.empty()) {
        node u = q.top(); q.pop();
        // cout << u.x << ' ' << u.y << ' ' << u.t << endl;   ///
        if(u.t > dp[u.x][u.y]) continue;
        for(int i = 0; i < 4; i++) {
            int xx = u.x + dir[i][0], yy = u.y + dir[i][1];
            if(xx < 1 || yy < 1 || xx > n || yy > m) continue;
            if(dp[u.x][u.y] + add[xx][yy] < dp[xx][yy]) {
                dp[xx][yy] = dp[u.x][u.y] + add[xx][yy];
                q.push((node){xx, yy, dp[xx][yy]});
            }
        }
    }
    return;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            scanf("%1d", &a[i][j]);
            if((i + j) % 2) add[i][j] = (a[i][j] == a[1][1]) + 1;
            else add[i][j] = (a[i][j] != a[1][1]) + 1;
        }
    }
    solve();
    cout << dp[n][m] << endl;
	return 0;
}