http://acm.nyist.net/JudgeOnline/problem.php?pid=58

本文主要是介绍http://acm.nyist.net/JudgeOnline/problem.php?pid=58，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

bfs搜索水题进行时~~~~

#include<iostream>
#include<string.h>
#include<cstdio>
#include<string>
#include<queue>
using namespace std;
int map[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 dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
struct point
{int x;int y;int step;
}po;
bool visit[10][10];
int sx,sy,ex,ey;
int step;
int bfs(int x,int y)
{memset(visit,false,sizeof(visit));queue<point>q;po.x=x;po.y=y;po.step=0;q.push(po);visit[x][y]=true;while(!q.empty()){po=q.front();q.pop();x=po.x;y=po.y;step=po.step;if(x==ex&&y==ey) return step;for(int i=0;i<4;++i){int x1=x+dx[i];int y1=y+dy[i];if(!map[x1][y1]&&!visit[x1][y1]&&x1>=0&&x1<=8&&y1>=0&&y1<=8){ po.x=x1;po.y=y1;po.step=step+1;q.push(po);visit[x1][y1]=true;}}}
}
int main()
{int T;cin>>T;while(T--){cin>>sx>>sy>>ex>>ey;cout<<bfs(sx,sy)<<endl;}return 0;
}

dfs

#include<iostream>
#include<string.h>
#include<cstdio>
#include<string>
#include<queue>
using namespace std;
int map[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 dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
struct point
{int x;int y;int step;
}po;
int sx,sy,ex,ey;
int step,minstep;
void dfs(int x,int y)
{if(x==ex&&y==ey) {minstep=min(step,minstep);return;}//结束条件for(int i=0;i<4;++i){int x1=dx[i]+x;int y1=dy[i]+y;if(x1>=0&&x1<=8&&y1>=0&&y1<=8&&!map[x1][y1]){step++;map[x1][y1]=1;dfs(x1,y1);map[x1][y1]=0;//回溯。。。。step--;}}
}
int main()
{int T;scanf("%d",&T);while(T--){    step=0;minstep=0xffffff;scanf("%d%d%d%d",&sx,&sy,&ex,&ey);map[sx][sy]=1;dfs(sx,sy);map[sx][sy]=0;printf("%d\n",minstep);}return 0;
}

这篇关于http://acm.nyist.net/JudgeOnline/problem.php?pid=58的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---