UVA 439 骑士（Knight Moves ）很基础的BFS

Bertha 。 2024-02-17 19:04 59阅读 0赞

#include<cstdio>
    #include<queue>
    #include<cstring>
    using namespace std;
    const int maxn=8+2; 
    struct node{
    	int x,y;
    	node(int x=0,int y=0):x(x),y(y){}
    };
    node ns,nt;
    int d[maxn][maxn];
    int dir[][2]={
       {1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1}};
    bool isValid(node & nd){
    	return nd.x>=1 && nd.x<=8 && nd.y>=1 && nd.y<=8;
    } 
    int bfs(){
    	memset(d,0,sizeof(d));
    	queue<node>q;
    	q.push(ns);
    	while(!q.empty()){
    		node u=q.front();
    		q.pop();
    		if(u.x==nt.x && u.y==nt.y)return d[u.x][u.y];
    		for(int i=0;i<8;i++){
    			node v=node(u.x+dir[i][0],u.y+dir[i][1]);
    			if(isValid(v) && !d[v.x][v.y]){
    				q.push(v);
    				d[v.x][v.y]=d[u.x][u.y]+1;
    			}
    		}
    	}
    } 
    int main(){
    	char s1[2],s2[2];
    	while(scanf("%s%s",s1,s2)==2){
    		ns.x=s1[0]-'a'+1;ns.y=s1[1]-'0';
    		nt.x=s2[0]-'a'+1;nt.y=s2[1]-'0';
    		int step=bfs();
    		printf("To get from %s to %s takes %d knight moves.\n",s1,s2,step);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，59人围观）

还没有评论，来说两句吧...

相关阅读

相关 UVA 439 骑士（Knight Moves ）很基础的BFS

include<cstdio> include<queue> include<cstring> using namespace std;

Bertha 。/ 2024年02月17日 19:04/ 0 赞/ 60 阅读

相关 HDU - 1372 Knight Moves（bfs入门）

HDU - 1372 Knight Moves 题目链接：[https://vjudge.net/problem/HDU-1372\author=swust2014156

刺骨的言语ヽ痛彻心扉/ 2023年08月17日 15:40/ 0 赞/ 114 阅读

相关 pku 1915 Knight Moves 双向BFS

最简单的双向BFS, 就不做注释和说明了-\_- \include <stdio.h> \include <iostream> \include <string.h> \in

拼搏现实的明天。/ 2022年08月18日 10:55/ 0 赞/ 121 阅读

相关 poj 1915 Knight Moves【BFS】【简单】

Knight Moves <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS<

待我称王封你为后i/ 2022年08月10日 09:29/ 0 赞/ 68 阅读

相关 POJ 1915-Knight Moves（BFS-跳马）

Knight Moves <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS

小灰灰/ 2022年06月17日 13:28/ 0 赞/ 133 阅读

相关 HDU-1372 Knight Moves (BFS)

Knight Moves Problem Description A

水深无声/ 2022年05月19日 00:25/ 0 赞/ 131 阅读

相关 UVA - 439——Knight Moves

[Knight Moves][] A friend of you is doing

末蓝、/ 2022年03月26日 03:41/ 0 赞/ 171 阅读

相关 (简单双向BFS)poj1915 Knight Moves

题目链接：[poj1915 Knight Moves][] 比起单向要省时得多。 include <iostream> include <cstdio>

àì夳堔傛蜴生んèń/ 2022年03月18日 08:50/ 0 赞/ 162 阅读

相关 Knight Moves UVA - 439 (BFS)

A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to

绝地灬酷狼/ 2022年02月26日 12:43/ 0 赞/ 181 阅读

相关 UVA——439 Knight Moves（搜索）

题目： Knight Moves Problem Description A friend of you is doing research on the Tra

痛定思痛。/ 2021年09月26日 11:36/ 0 赞/ 197 阅读