Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:这道题能深搜做么

Posted by fangpin at 2014-12-29 16:04:38 on Problem 1915
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator