题目链接
数据范围
n,m <= 1e3
题解
构建分层图，\((i , j , 0 / 1)\) 表示在矩阵的\((i , j)\) 位置上，当前状态为\(0 / 1\) 的点。
如果要到达的点和当前点的状态不同，则可以花费时间1到达。
如果状态相同，则要先花费时间1改变目标点的状态再走，共花费时间2.
然后就是跑最短路了。
另外
讲题的大佬还说若想要优化掉log，可以根据这题的距离很小的特性优化\(Dij\)，开一些队列\(q[N]\),其中\(q[i]\)表示dis为\(i\)的点有哪些.
这样找未更新的点中dis最小的点就是寻找第一个非空队列。
虽然没有尝试过，但是感觉这个常数应该会比log要大一些吧，在总距离小的时候应该很管用。
一直搞不太清楚怎么建图，开始的时候将不同层不同点连1的边，相同层不同点连2的边，在将状态0和状态1之间连边。但是很尴尬的是，发现这个图的建立和读入数据没有了关系……
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N = 1010;
int n , m , Cnt;
int A[N][N] , head[N * N * 2] , D[N * N * 2] , Vis[N * N * 2];
struct edge{ int v , nex , c; }e[N * N * 2 * 4 * 2];
inline int id(int x , int y , int op)
{
return (x - 1) * m + y + op * n * m;
}
inline void add(int u , int v , int c)
{
e[++Cnt].v = v; e[Cnt].c = c; e[Cnt].nex = head[u]; head[u] = Cnt;
}
int main()
{
queue<int> q;
int a , b , x;
const int dx[] = {1 , -1 , 0 , 0};
const int dy[] = {0 , 0 , 1 , -1};
scanf("%d%d" , &n , &m);
for(int i = 1 ; i <= n ; ++i)
for(int j = 1 ; j <= m ; ++j)
scanf("%1d" , &A[i][j]);
for(int i = 1 ; i <= n ; ++i)
for(int j = 1 ; j <= m ; ++j)
{
for(int k = 0 ; k < 4 ; ++k)
{
a = i + dx[k]; b = j + dy[k];
if(a < 1 || a > n || b < 1 || b > m) continue;
add(id(i , j , 0) , id(a , b , 1) , 1 + (0 == A[a][b]));
add(id(i , j , 1) , id(a , b , 0) , 1 + (1 == A[a][b]));
}
}
q.push(id(1 , 1 , A[1][1]));
for(int i = 1 ; i <= n ; ++i)
for(int j = 1 ; j <= m ; ++j)
D[id(i , j , 0)] = D[id(i , j , 1)] = 1e8;
D[id(1 , 1 , A[1][1])] = 0; Vis[id(1 , 1 , A[1][1])] = 1;
while(q.size())
{
x = q.front(); q.pop(); Vis[x] = 0;
for(int i = head[x] ; i ; i = e[i].nex)
{
int v = e[i].v;
if(D[v] > D[x] + e[i].c)
{
D[v] = D[x] + e[i].c;
if(!Vis[v]) Vis[v] = 1 , q.push(v);
}
}
}
printf("%d\n" , min(D[id(n , m , 0)] , D[id(n , m , 1)]));
return 0;
}
/*
4 4
1111
1111
1010
0101
*/