这里写链接内容
题目意思：不用翻译了，就是给定一个最多转弯的数目，让求如果她所走的转弯次数不超过k，问她能不能到达目的地
思路：这道题刚开始用的广搜，中间出现了很多bug 都来跳不出来了，又看看博客，广搜就是在一个方向上一直搜，搜不到了换方向，直到搜到为止且转弯数小于等于k,这是广搜的思路
#include<stdio.h> #include<iostream> #include<algorithm> #include<queue> #include<string.h> using namespace std; int m,n,k,x1,y1,x2,y2; int i,j,flag; char maze[105][105],s; int vis[105][105]; int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}}; struct node { int x; int y; int step; }; void bfs() { queue<node>q; node a,b; a.x=x1-1; a.y=y1-1; a.step=-1; vis[a.x][a.y]=1; q.push(a); while(!q.empty()) { a=q.front(); q.pop(); if(a.x==(x2-1)&&a.y==(y2-1)&&a.step<=k) { // printf("%d\n",a.step); flag=1; break; } b.step=a.step+1; for(i=0; i<4; i++) { int w=a.x+dir[i][0]; int e=a.y+dir[i][1]; while(w>=0&&w<n&&e>=0&&e<m&&maze[w][e]!='*') { if(vis[w][e]==0) { vis[w][e]=1; b.x=w; b.y=e; q.push(b); } w=w+dir[i][0]; e=e+dir[i][1]; } } } if(flag==1) printf("yes\n"); else printf("no\n"); } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(i=0; i<n; i++) { scanf("%s",maze[i]); } cin>>k>>y1>>x1>>y2>>x2; memset(vis,0,sizeof(vis)); flag=0; bfs(); } return 0; }说下深搜的思路就是主要的剪枝的部分，我对神搜感觉不会，这个是参考别人的代码，有点迷迷糊糊的，了解的一知半解
#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<map> #include<queue> #define LL long long using namespace std; const int MAX=10000; const int N=110; int dir[4][2]={{-1,0}, {0,1}, {1,0},{0,-1}}; int vis[N][N],turn[N][N],flag; char maze[N][N]; int t,n,m; int k,x1,y1,x2,y2; struct node { int x,y; }; bool judge(int x,int y) { if(x>=0&&x<m&&y>=0&&y<n&&maze[x][y]!='*') return true; return false; } void dfs(int x,int y,int mov) { if(x==x2&&y==y2&&turn[x][y]<=k) { flag=1; return ; } if(turn[x][y]>k) return; if(x!=x2&&y!=y2&&turn[x][y]>=k) return ; for(int i=0;i<4;i++) { int xx=x+dir[i][0]; int yy=y+dir[i][1]; if(!judge(xx,yy)) { continue; } if(turn[xx][yy]<turn[x][y]) continue; if(mov!=-1&&mov!=i&&turn[xx][yy]<turn[x][y]+1) continue; if(mov!=-1&&mov!=i) turn[xx][yy]=turn[x][y]+1; else turn[xx][yy]=turn[x][y]; maze[xx][yy]='*'; dfs(xx,yy,i); maze[xx][yy]='.'; if(flag) return ; } } int main() { scanf("%d",&t); while(t--) { scanf("%d %d",&m,&n); for(int i=0;i<m;i++) { scanf("%s",maze[i]); } cin>>k>>y1>>x1>>y2>>x2; memset(turn,0x3f3f3f3f,sizeof(turn)); y1--; x1--; y2--; x2--; turn[x1][y1]=0; flag=0; dfs(x1,y1,-1); if(flag) printf("yes\n"); else printf("no\n"); } return 0; }参考链接
