https://ac.2333.moe/Problem/view.xhtml?id=1642
第一种情况直接用个BFS优先队列就可以了。
第二种情况对路径进行记录，采用三维数组防止死循环。
#include<cstdio> #include<iostream> #include<cstring> #include<queue> #include<algorithm> using namespace std; char s[100]; int n,m,r1,c1,r2,c2,ans1,ans2; int map[600][600],vis[600][600],use[600][600][5]; int dir[4][2]={1,0,0,1,-1,0,0,-1}; struct node{ int x,y,sum,op; }; bool operator<( node a, node b ){ return a.sum>b.sum; } int check(int x,int y) { if(x>=0&&x<n&&y>=0&&y<m) return 1; return 0; } void bfs1() { priority_queue<node>Q; node p,q,next; p.x=r1;p.y=c1; memset(vis,0,sizeof(vis)); vis[p.x][p.y]=1; p.sum=map[r1][c1]; Q.push(p); while(!Q.empty()) { q=Q.top(); Q.pop(); if(q.x==r2&&q.y==c2) { ans1=q.sum; return; } for(int i=0;i<4;i++) { next.x=q.x+dir[i][0]; next.y=q.y+dir[i][1]; if(!check(next.x,next.y)||vis[next.x][next.y]||map[next.x][next.y]==-1) continue; next.sum=q.sum+map[next.x][next.y]; vis[next.x][next.y]=1; Q.push(next); } } return; } void bfs2() { priority_queue<node>Q; node p,q,next; p.x=r1;p.y=c1; p.sum=map[r1][c1]; memset(use,0,sizeof(use)); p.op=-1; Q.push(p); while(!Q.empty()) { q=Q.top(); Q.pop(); if(q.x==r2&&q.y==c2) { ans2=q.sum; return; } for(int i=0;i<4;i++) { if(i==q.op) continue; next.x=q.x+dir[i][0]; next.y=q.y+dir[i][1]; if(!check(next.x,next.y)||use[q.x][q.y][i]||map[next.x][next.y]==-1) continue; next.sum=q.sum+map[next.x][next.y]; use[q.x][q.y][i]=1; next.op=i; Q.push(next); } } return; } main() { int i,j,k,cas=1; while(scanf("%d%d%d%d%d%d",&n,&m,&r1,&c1,&r2,&c2)!=EOF) { r1--,r2--,c1--,c2--; for(i=0;i<n;i++) { for(j=0;j<m;j++) { scanf("%s",s); int len=strlen(s);int vir=0; if(s[0]=='*') map[i][j]=-1; else { for(k=0;k<len;k++) vir=vir*10+s[k]-'0'; map[i][j]=vir; } } } ans1=-1;ans2=-1; bfs1(); bfs2(); printf("Case %d: %d %d ",cas++,ans1,ans2); } }