題目

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

題意是說，給你一張 \(n * m(n,m \leq 10^3)\) 大小的01地圖，當(dāng)前點(diǎn)下一步只能走到相鄰的點(diǎn)上，如果這兩個點(diǎn)值相同，則代價為2，否則代價為1，問從（1，1）走到（n，m）最少代價是多少

思路

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

那么狀態(tài)轉(zhuǎn)移就不能兩層循環(huán)解決了，有點(diǎn)類似dp，但是實(shí)現(xiàn)需要用到bfs，bfs的依據(jù)是從當(dāng)前代價最小的狀態(tài)的點(diǎn)開始往其他地方轉(zhuǎn)移，因此使用優(yōu)先隊(duì)列

具體來說，因?yàn)閺牡谝粋€點(diǎn)開始走的路徑上的值一定是010101...或者101010....，所以先根據(jù)從起點(diǎn)開始走到的奇數(shù)or偶數(shù)步給每個點(diǎn)一個初始的cost，再把他們修改為相應(yīng)的0或1；

bfs的時候如果當(dāng)前的代價大于這個點(diǎn)的最小代價，就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;
}