题目
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;
}