B - Knight Moves
程序员文章站
2022-04-29 10:40:18
题目该题是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 =...
题目
该题是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
上一篇: A - Oil Deposits