| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:这道题能深搜做么In Reply To:这道题能深搜做么 Posted by:pengky at 2014-12-19 22:08:44 > 如果能,指导一下吧。。。谢谢
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
bool vis[310][310];//标记数组
int n;
int dx[]={-1,-2,-2,-1,1,2,2,1},dy[]={2,1,-1,-2,-2,-1,1,2};//方向数组
struct P{//点类
int x,y;
};
struct Node{//队元素
P x;
int step;
};
int bfs(P a,P b){
memset(vis,false,sizeof(vis));
vis[a.x][a.y]=true;
Node now,next;
now.x=a;now.step=0;
queue<Node> q;//用队列实现bfs
q.push(now);
while(!q.empty()){
now=q.front();q.pop();
if(now.x.x==b.x && now.x.y==b.y){
return now.step;
}
for(int i=0;i<8;++i){
int xx=next.x.x=now.x.x+dx[i],yy=next.x.y=now.x.y+dy[i];
next.step=now.step+1;
if(xx>=0 && xx<n && yy>=0 && yy<n && !vis[xx][yy]){
vis[xx][yy]=true;
q.push(next);
}
}
}
return 0;
}
int main()
{
int t;scanf("%d",&t);
while(t--){
scanf("%d",&n);
P a,b;
scanf("%d%d%d%d",&a.x,&a.y,&b.x,&b.y);
int ans=bfs(a,b);
printf("%d\n",ans);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator