网格图转向最短路问题

题目描述给定一个 × 的网格每个格子标记为A、B或C类型。从起点 (1,1) 出发初始方向向右目标到达 (,1)网格右侧外一格且方向向右。在不同的格子类型中转向有不同的代价规则A 格直行不消耗代价左右转消耗 1B 格左转不消耗代价直行和右转消耗 1C 格右转不消耗代价直行和左转消耗 1求从起点到终点的最小总代价。输入格式多组测试数据每组包含网格大小 ,× 的网格每个格子为A、B或C输出格式每组数据输出一个整数表示最小代价。算法思路状态设计使用三元组 (,,) 表示状态(,)当前坐标当前朝向1→右2↑上3↓下4←左核心算法Dijkstra优先队列 BFS由于转向代价不同使用Dijkstra 算法求最短路。方向编码1: → (右)2: ↑ (上)3: ↓ (下)4: ← (左)CODE#includebits/stdc.h #define wk(x) write(x),putchar( ) #define wh(x) write(x),putchar(\n) #define int long long #define INF 2147483647 #define mod 998244353 #define N 610005 #define NO printf(No\n) #define YES printf(Yes\n) using namespace std; int n,m,k,jk,ans,sum,num,cnt,tot; int dis[N],vis[N][5],f[N]; char a[N]; void read(int x){ x0;int ff1;char ty; tygetchar(); while(!(ty0ty9)){ if(ty-) ff-1; tygetchar(); } while(ty0ty9) x(x3)(x1)ty-0,tygetchar(); x*ff;return; } void write(int x){ if(x0){ putchar(0); return; } if(x0){ x-x; putchar(-); } char asd[201];int ip0; while(x) asd[ip]x%100,x/10; for(int iip;i1;i--) putchar(asd[i]); return; } struct Q{ int sum,x,y,fx; bool operator(const QA)const{ return A.sumsum; } }; priority_queueQ q; /* 1:- 2:^ 3:v 4:- */ int pd(int x,int fx){ if(x1){ return fx; }else if(x2){ if(fx1) return 3; if(fx2) return 4; if(fx3) return 1; if(fx4) return 2; }else{ if(fx1) return 2; if(fx2) return 1; if(fx3) return 4; if(fx4) return 3; }return 0; } pairint,int G(int x,int y,int fx){ if(fx1) return {x,y1}; if(fx2) return {x-1,y}; if(fx3) return {x1,y}; if(fx4) return {x,y-1}; return {0,0}; } void bfs(){ while(!q.empty()) q.pop(); q.push((Q){0,1,1,1}); while(!q.empty()){ Q Aq.top();q.pop();//wk(A.x),wk(A.y);wh(A.sum); if(A.xnA.ym1A.fx1) {ansA.sum;return;} if(A.x1||A.y1||A.xn||A.ym||vis[A.x*mA.y][A.fx]!2e9) continue; vis[A.x*mA.y][A.fx]A.sum; if(a[A.x*mA.y]A){ pairint,int toG(A.x,A.y,pd(1,A.fx)); if(vis[to.first*mto.second][pd(1,A.fx)]2e9) q.push((Q){A.sum,to.first,to.second,pd(1,A.fx)}); toG(A.x,A.y,pd(2,A.fx)); if(vis[to.first*mto.second][pd(2,A.fx)]2e9) q.push((Q){A.sum1,to.first,to.second,pd(2,A.fx)}); toG(A.x,A.y,pd(3,A.fx)); if(vis[to.first*mto.second][pd(3,A.fx)]2e9) q.push((Q){A.sum1,to.first,to.second,pd(3,A.fx)}); }else if(a[A.x*mA.y]B){ pairint,int toG(A.x,A.y,pd(2,A.fx)); if(vis[to.first*mto.second][pd(2,A.fx)]2e9) q.push((Q){A.sum,to.first,to.second,pd(2,A.fx)}); toG(A.x,A.y,pd(1,A.fx)); if(vis[to.first*mto.second][pd(1,A.fx)]2e9) q.push((Q){A.sum1,to.first,to.second,pd(1,A.fx)}); toG(A.x,A.y,pd(3,A.fx)); if(vis[to.first*mto.second][pd(3,A.fx)]2e9) q.push((Q){A.sum1,to.first,to.second,pd(3,A.fx)}); }else{ pairint,int toG(A.x,A.y,pd(3,A.fx)); if(vis[to.first*mto.second][pd(3,A.fx)]2e9) q.push((Q){A.sum,to.first,to.second,pd(3,A.fx)}); toG(A.x,A.y,pd(1,A.fx)); if(vis[to.first*mto.second][pd(1,A.fx)]2e9) q.push((Q){A.sum1,to.first,to.second,pd(1,A.fx)}); toG(A.x,A.y,pd(2,A.fx)); if(vis[to.first*mto.second][pd(2,A.fx)]2e9) q.push((Q){A.sum1,to.first,to.second,pd(2,A.fx)}); } } } signed main() { read(jk);while(jk--){ read(n),read(m); for(int i1;in;i){ for(int j1;jm;j){ char chgetchar(); while(ch!Ach!Bch!C) chgetchar(); a[i*mj]ch; } } for(int i0;in*mm;i) vis[i][1]vis[i][2]vis[i][3]vis[i][4]0; vis[n*mm1][1]2e9; for(int im1;in*mm;i) vis[i][1]vis[i][2]vis[i][3]vis[i][4]2e9; ans2e9;bfs();wh(ans); } return 0; }