poj 2243（bfs结构体）

本文主要是介绍poj 2243（bfs结构体），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
int ans;
int data[10][10],visit[10][10];
struct Node{
    int x,y;
    Node(int a,int b):x(a),y(b){
    }
    Node(){
        x = -1;
        y = -1;
    }
};
Node pre[10][10];
queue<Node>q; 
bool bfs(Node node){
    q.push(node);
    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        Node u(x,y);
        q.pop();
        if(data[x][y]==-2){
            while(!q.empty())
                q.pop();
            return true;
        }
        else{
            if(x-1>=1&&y-2>=1&&visit[x-1][y-2]==0){
                q.push(Node(x-1,y-2));
                visit[x-1][y-2] = 1;
                pre[x-1][y-2] = u;
            }
            if(x-1>=1&&y+2<=8&&visit[x-1][y+2]==0){
                q.push(Node(x-1,y+2));
                visit[x-1][y+2] = 1;
                pre[x-1][y+2] = u;
            }
            if(x-2>=1&&y-1>=1&&visit[x-2][y-1]==0){
                q.push(Node(x-2,y-1));
                visit[x-2][y-1] = 1;
                pre[x-2][y-1] = u;
            }
            if(x-2>=1&&y+1<=8&&visit[x-2][y+1]==0){
                q.push(Node(x-2,y+1));
                visit[x-2][y+1] = 1;
                pre[x-2][y+1] = u;
            }
            if(x+1<=8&&y-2>=1&&visit[x+1][y-2]==0){
                q.push(Node(x+1,y-2));
                visit[x+1][y-2] = 1;
                pre[x+1][y-2] = u;
            }
            if(x+1<=8&&y+2<=8&&visit[x+1][y+2]==0){
                q.push(Node(x+1,y+2));
                visit[x+1][y+2] = 1;
                pre[x+1][y+2] = u;
            }
            if(x+2<=8&&y-1>=1&&visit[x+2][y-1]==0){
                q.push(Node(x+2,y-1));
                visit[x+2][y-1] = 1;
                pre[x+2][y-1] = u;
            }
            if(x+2<=8&&y+1<=8&&visit[x+2][y+1]==0){
                q.push(Node(x+2,y+1));
                visit[x+2][y+1] = 1;
                pre[x+2][y+1] = u;
            }
        }
    }
}
int main(){
    char a[5],b[5];
    while(scanf("%s%s",a,b)==2){
        memset(data,0,sizeof data);
        memset(visit,0,sizeof visit);
        memset(pre,0,sizeof pre);
        int x = a[0]-'a'+1;
        int y = a[1]-'1'+1;
        data[x][y] = -1;
        int p = b[0]-'a'+1;
        int q = b[1]-'1'+1;
        data[p][q] = -2;
        visit[x][y] = 1;
        Node node(x,y);
        bfs(node);
        ans = 0;
        if(x==p&&y==q){
            printf("To get from %s to %s takes 0 knight moves.\n",a,b);
            continue;
        } 
        while(true){
            int tp = pre[p][q].x;
            int tq = pre[p][q].y;
            ans++;
            if(data[tp][tq]==-1){
                break;
            }
            p = tp;
            q = tq;
        }
        printf("To get from %s to %s takes %d knight moves.\n",a,b,ans);
    }
    return 0;
}

这篇关于poj 2243（bfs结构体）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！