当前位置： 移动技术网 > IT编程>开发语言>Java > B - Knight Moves

B - Knight Moves

2020年07月12日  | 移动技术网IT编程  | 我要评论

题目
该题是BFS的模板题，要找一个点道另一个点的最小步数，感觉这题对BFS的理解比较好，在之前看过一些BFS的视频博客，都没有特别理解，然后看了这题感觉理解加深多了，因为要找最少的，所以用bfs,不能dfs,会超时
通过维护一个队列，依次找到最小的
AC代码：

import java.io.*;
import java.math.*;
import java.math.BigInteger;
import java.util.*;
public class Main{
	static int[] dr = {-2,-2,-1,1,2,2,1,-1};
	static int[] dc = {-1,1,2,2,1,-1,-2,-2};
	static boolean[][] vis = new boolean[9][9];
	static int ans;
	static int start_x,start_y,end_x,end_y;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while(scan.hasNext()){
			for(int i=1;i<=8;i++){
				Arrays.fill(vis[i], false);
			}
			String start = scan.next();
			String end = scan.next();
			start_x = start.charAt(0)-'a'+1;
			start_y = 9-(start.charAt(1)-'0');
			end_x = end.charAt(0)-'a'+1;
			end_y = 9-(end.charAt(1)-'0'); 
			Queue<Node> q = new LinkedList<Node>();//装自己写的方法
			Node u = new Node(start_x,start_y,0);
			q.add(u);
			while(!q.isEmpty()){
				u = q.poll();//poll函数删除并返回头部元素
				if(u.r==end_x&&u.c==end_y){
					System.out.printf("To get from %s to %s takes %d knight moves.\n",start,end,u.d);
					break;
				}
				for(int i=0;i<8;i++){//队列更新
					int r = u.r+dr[i];
					int c = u.c+dc[i];
					if(inside(r,c)){
						q.add(new Node(r,c,u.d+1));
					}
				}
			}
		}
	}
	
	public static boolean inside(int r,int c){//判断是否越界
		return r>=1&&r<=8&&c>=1&&c<=8;
	}
	static class Node{//三个数对应x,y,步数
		int r,c,d;
		public Node(int r,int c,int d){
			this.r = r;
			this.c = c;
			this.d = d;
		}
	}
}

本文地址：https://blog.csdn.net/nankes/article/details/107273048

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网