D-矩阵_牛客小白月赛75 (nowcoder.com)

讯享网

思路：一个点有两种不同的状态，我们很容易想到分层图，对于分层图，有两种解法，一种是把所有边全部建好后去跑最短路，另一种就是在跑最短路的过程中加入一维状态去进行记录。对于第一种方法，难在建图，建完图后跑最短路的方式和原来无异，对于第二种方法，因为加入状态一栏，所以有点类似于dp状态转移的感觉，相比于第一种就难理解点。

法一：建完边再跑最短路：

建边思路：首先我们把这个图分为两层，对于我们走到点u，我们会对四个方向进行建边，而每一层的内部不会存在边，边只存在于层于层之间，对于点u，第0层会向第一层建一条边，而该边的边权取决于对应的点v是否在第一层，即a[v]是否为1，因为当a[v]为1时，我们可以直接走到该点，不需要对该点进行翻转，反之则边权为2，对于u的第二层也同理。

总上所述，我们需要2*n*m个点，还有一点就是对点进行编号，我们对第一层的点编号为1-n*m，对于第二层的点，我们在第一层对应的点编号上加上n*m即可，例如点u的第一层编号为x，那么第二层编号即为x+n*m。

#include <bits/stdc++.h> using namespace std; const int N = 2e6 + 5; typedef long long ll; const int maxv = 4e6 + 5; typedef pair<ll, ll> pll; int n, m; char a[1005][1005]; int get(int a,int b) { return (a-1)*m+b; } vector<pll> e[N]; void add(int u,int v,int w) { e[u].push_back({w,v}); } ll st[N],d[N]; int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; void dijkstra(int c) { priority_queue<pll ,vector<pll>,greater<pll>> q; memset(d,0x3f,sizeof( d)); d[c]=0; q.push({0,c}); while(!q.empty()){ auto x=q.top(); q.pop(); int ver=x.second; int dis=x.first; if(st[ver]) continue; st[ver]=1; for(auto v: e[ver]){ int disn=v.first; int vern=v.second; if(d[vern]>d[ver]+disn){ d[vern]=d[ver]+disn; q.push({d[vern],vern}); } } } cout<<min(d[n*m],d[n*m*2])<<endl; } void solve() { cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; } } int t=n*m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ for(int k=0;k<4;k++){ int nx=dx[k]+i,ny=dy[k]+j; if(nx<1||nx>n||ny<1||ny>m) continue; int u,v; u=get(i,j),v=get(nx,ny)+t; if(a[nx][ny]=='1') add(u,v,1); else add(u,v,2); u=get(i,j)+t,v=get(nx,ny);; if(a[nx][ny]=='1') add(u,v,2); else add(u,v,1); } } } if(a[1][1]=='1') dijkstra(1+n*m); else dijkstra(1); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) { solve(); } system("pause"); return 0; }

 法二：加入状态一维，对于这一维的状态，我们既可加到求最短路的数组d[N]中，又可在队列中加入这一变量，我们对所有的状态和1进行1异或即可。

对于队首所衍生点的状态是根据队首的状态进行确定的，例如111，第二个1的状态为0，因为队首的1^1=0，而对于第三个元素的状态，是根据第二个元素的状态进行判定，因为第二个元素状态为0，0^1=1，所以第三个元素的状态为1，依次类推。

讯享网#include<bits/stdc++.h> using namespace std; const int N=5e5+5; typedef long long ll; typedef pair<ll,ll> pll; int mod=1e9+7; const int maxv=4e6+5; int n,m; char a[1005][1005]; int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; int d[1005][1005]; void solve() { cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) cin>>a[i][j]; } memset(d,0x3f,sizeof d); queue<array<int,3>> q; d[1][1]=0; q.push({1,1,a[1][1]-'0'}); while(!q.empty()){ auto [x,y,z]=q.front(); q.pop(); for(int i=0;i<4;i++){ int nx=dx[i]+x,ny=dy[i]+y; if(nx<1||nx>n||ny<1||ny>m) continue; int s=a[nx][ny]-'0'; if(s!=z){ if(d[nx][ny]>d[x][y]+1) { d[nx][ny]=d[x][y]+1; q.push({nx,ny,z^1}); } } else{ if(d[nx][ny]>d[x][y]+2){ d[nx][ny]=d[x][y]+2; q.push({nx,ny,z^1}); } } } } cout<<d[n][m]<<endl; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; t=1; //cin>>t; while(t--){ solve(); } system("pause"); return 0; }