今日题目：牛
题目分析
题目难度：⭐️⭐️
题目涉及算法：最短路，图论，dfs，bfs。
ps：有能力的小伙伴可以尝试优化自己的代码或者一题多解，这样能综合提升自己的算法能力
题解报告：
1.思路
解法1dfs：
我们定义一个ans值为正无穷，在进行搜索的时候如果遇到b就取最小值并返回，如果搜索的路比当前ans值大说明错了也返回，剩下的就是加一个回溯往下搜索，时间为112ms（应该是）
解法2bfs：
同样需要一个ans，在队列内循环判断的时候每次都找最短的哪一个，记得记录起点终点，其他的就是正常的bfs了。
解法三spfa：
（我真的好喜欢队列）这就按照正常的模板，然后搞一个数组保存路径，出来之后判断最短的哪一个！不懂得看这个文章spfa
2.代码
DFS
#include<bits/stdc++.h> using namespace std; const int N = 1001; char s[N][N]; int st[N][N]; int ans=0x3f3f3f3f; int lx,ly,fx,fy,n; int dx[]={1,-1,0,0}; int dy[]={0,0,-1,1}; void dfs(int x,int y,int sum,int num) { if(s[x][y]=='B') { ans=min(ans,sum); return ; } if(sum>=ans) { return ; } for(int i=0;i<4;i++) { int xx=x+dx[i]; int yy=y+dy[i]; if(xx>=0&&xx<n&&yy>=0&&yy<n&&!st[xx][yy]&&s[xx][yy]!='x') { if(num==-1) { st[xx][yy]=1; dfs(xx,yy,sum,i); st[xx][yy]=0; } else if(num!=i) { st[xx][yy]=1; dfs(xx,yy,sum+1,i); st[xx][yy]=0; } else { st[xx][yy]=1; dfs(xx,yy,sum,i); st[xx][yy]=0; } } } } int main() { cin>>n; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cin>>s[i][j]; } } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(s[i][j]=='A') { st[i][j] = 1; dfs(i,j,0,-1); } } } if(ans==0x3f3f3f3f) { cout<<"-1"; } else { cout<<ans; } return 0; }
BFS：
#include <bits/stdc++.h> using namespace std; const int N=1001; char s[N][N]; int st[N][N]; int dist[N][N]; int lx,ly,fx,fy,n; int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; int flag,ans=0x3f3f3f3f; struct node{ int x,y,num; }; int check(int x,int y) { if(x>=1&&x<=n&&y>=1&&y<=n&&s[x][y]!='x') { return true; } return false; } void bfs() { if(lx==fx&&ly==fy) { flag=1; ans=0; return ; } queue<node>q; q.push({lx,ly,-1}); st[lx][ly]=1; while(q.size()) { node t=q.front(); q.pop(); for(int i=0;i<4;i++) { int x=t.x+dx[i]; int y=t.y+dy[i]; int cnt=t.num+1; while(check(x,y)) { if(!st[x][y]) { st[x][y]=1; q.push({x,y,cnt}); if(x==fx&&y==fy) { flag=1; ans=min(ans,cnt); return ; } } x+=dx[i]; y+=dy[i]; } } } } int main() { cin>>n; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cin>>s[i][j]; if(s[i][j]=='A') { lx=i; ly=j; } else if(s[i][j]=='B') { fx=i; fy=j; } } } bfs(); if(flag) { cout<<ans; return 0; } cout<<"-1"; return 0; }
spfa：
#include<bits/stdc++.h> using namespace std; const int N = 1001; char s[N][N]; int lx,ly,fx,fy,n; int vis[N][N][4],dis[N][N][4]; struct node{ int x,y,num; }; int dx[]={1,-1,0,0}; int dy[]={0,0,-1,1}; bool pd(int x,int y) { if(x<1||y<1||x>n||y>n||s[x][y]=='x') { return true; } return false; } void spfa() { queue<node>q; memset(dis,0x3f3f3f3f,sizeof(dis)); for(int i=0;i<4;i++) { q.push({lx,ly,i}); dis[lx][ly][i]=0; } while(q.size()) { node t=q.front(); q.pop(); vis[t.x][t.y][t.num]=0; for(int i=0;i<4;i++) { int xx=t.x+dx[i],yy=t.y+dy[i]; if(pd(xx,yy)) { continue; } int dd=(i!=t.num); if(dis[xx][yy][i]>dis[t.x][t.y][t.num]+dd) { dis[xx][yy][i]=dis[t.x][t.y][t.num]+dd; if(vis[xx][yy][i]==0) { q.push({xx,yy,i}); vis[xx][yy][i]=1; } } } } } int main() { cin>>n; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cin>>s[i][j]; if(s[i][j]=='A') { lx=i; ly=j; } if(s[i][j]=='B') { fx=i; fy=j; } } } spfa(); int sum=0x3f3f3f3f; for(int i=0;i<4;i++) { sum = min(sum,dis[fx][fy][i]); } if(sum==0x3f3f3f3f) { cout<<"-1"; } else { cout<<sum; } return 0; }
![贤鱼的刷题日常-P1021 [NOIP1999 提高组] 邮票面值设计-题目详解](https://ucc.alicdn.com/images/user-upload-01/82396d7e07e7417eb32de7487afbd3d3.gif?x-oss-process=image/resize,h_160,m_lfit)
