本文共 2099 字，大约阅读时间需要 6 分钟。

DFS+记忆化搜索

 /*

 qq:1239198605  ctgu_yyf         */ #include<iostream> #include<cstdio> #include<string> #include<vector> #include<queue> #include<stack> #include<cstring> #include<algorithm> #include<cmath> const int INF=10001; using namespace std; int mapp[9][9]={ 1,1,1,1,1,1,1,1,1,  1,0,0,1,0,0,1,0,1,  1,0,0,1,1,0,0,0,1,  1,0,1,0,1,1,0,1,1,  1,0,0,0,0,1,0,0,1,  1,1,0,1,0,1,0,0,1,  1,1,0,1,0,1,0,0,1,  1,1,0,1,0,0,0,0,1,  1,1,1,1,1,1,1,1,1, }; int vis[9][9];  int dp[9][9]; int xx[4]={0,1,0,-1}; int yy[4]={1,0,-1,0}; bool inmap(int x,int y) { if(x>=0&&x<=8&&y>=0&&y<=8) return true; return false; } int dfs(int sx,int sy,int ex,int ey) { int nx,ny; if(dp[sx][sy]!=INF) { return dp[sx][sy]; } if(sx==ex&&sy==ey) return 0; for(int i=0;i<4;i++) { nx=sx+xx[i]; ny=sy+yy[i]; if(inmap(nx,ny)&&vis[nx][ny]==0&&mapp[nx][ny]==0) { vis[nx][ny]=1; dp[sx][sy]=min((1+dfs(nx,ny,ex,ey)),dp[sx][sy]); vis[nx][ny]=0; } } return dp[sx][sy]; } int main() { int t; cin>>t; while(t--) { int sx,sy,ex,ey; for(int i=0;i<9;i++) for(int j=0;j<9;j++) { dp[i][j]=INF; } memset(vis,0,sizeof(vis)); cin>>sx>>sy>>ex>>ey; vis[sx][sy]=1; cout<<dfs(sx,sy,ex,ey)<<endl; } return 0;

}

BFS

#include<stdio.h>

#include<queue> #include<string.h> #include<algorithm> const int N = 9; bool vis[N][N]; int map[N][N]= {     1,1,1,1,1,1,1,1,1,     1,0,0,1,0,0,1,0,1,     1,0,0,1,1,0,0,0,1,     1,0,1,0,1,1,0,1,1,     1,0,0,0,0,1,0,0,1,     1,1,0,1,0,1,0,0,1,     1,1,0,1,0,1,0,0,1,     1,1,0,1,0,0,0,0,1,     1,1,1,1,1,1,1,1,1, }; using namespace std; int px[4]= {1,-1,0,0}; int py[4]= {0,0,1,-1}; int x,y,ex,ey; struct note{     int x,y;     int step; }; int bfs(){     note s;     s.x=x,s.y=y,s.step=0;     vis[x][y]=true;     queue<note>que;     que.push(s);     while(!que.empty()){         note now=que.front();         que.pop();         if(now.x==ex&&now.y==ey){             return now.step;         }         for(int l=0;l<4;l++){             note end;             end.x=now.x+px[l];             end.y=now.y+py[l];             end.step=now.step;             if(vis[end.x][end.y]==false&&map[end.x][end.y]==0){                 vis[end.x][end.y]=true;                 end.step+=1;                 que.push(end);             }         }     } } int main() {     int T;     scanf("%d",&T);     while(T--){         memset(vis,false,sizeof(vis));         scanf("%d%d%d%d",&x,&y,&ex,&ey);         int ans=bfs();         printf("%d\n",ans);     }     return 0; }

转载地址：https://blog.csdn.net/k_koris/article/details/80314595 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！