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