Poj1915 Knight Moves java
タイトルリンク:http://poj.org/problem?id=1915
テーマ:
あなたの任務は、別の場所から移動する最小限のステップ数を計算するプログラムを作成することです.そうすれば、Somurolovよりも速くなる機会があります.よく知られていないチェスかもしれないが、騎士の行動は図1に示すようになるかもしれない.入力はまず最初の行にnを入力し,n種類がある場合を表す.次はnスキームです.各シナリオには3行が含まれます.1行目は、1つの碁盤の長さL(4<=L<=300)を指定します.碁盤全体のサイズL*L.2行目と3行目は整数対(0,...,L-1)*(0,...,L-1)で騎士の開始位置と終了位置を指定します.整数ペアは空白で区切られます.出力は入力ごとに騎士の行動を計算し、始点から終点までの最低ステップ数を移動する必要がある場合です.始点と終点が平等であれば、距離はゼロです.
問題解決の考え方:
広さ探索は,開始点から毎回8方向に探索する.ゴールに着くまで.
MACコードは以下の通りである.
テーマ:
あなたの任務は、別の場所から移動する最小限のステップ数を計算するプログラムを作成することです.そうすれば、Somurolovよりも速くなる機会があります.よく知られていないチェスかもしれないが、騎士の行動は図1に示すようになるかもしれない.入力はまず最初の行にnを入力し,n種類がある場合を表す.次はnスキームです.各シナリオには3行が含まれます.1行目は、1つの碁盤の長さL(4<=L<=300)を指定します.碁盤全体のサイズL*L.2行目と3行目は整数対(0,...,L-1)*(0,...,L-1)で騎士の開始位置と終了位置を指定します.整数ペアは空白で区切られます.出力は入力ごとに騎士の行動を計算し、始点から終点までの最低ステップ数を移動する必要がある場合です.始点と終点が平等であれば、距離はゼロです.
問題解決の考え方:
広さ探索は,開始点から毎回8方向に探索する.ゴールに着くまで.
MACコードは以下の通りである.
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
public class Main{
static LinkedList list=new LinkedList();
static int visited[][]=new int[305][305];
// 8
static int direction[][]={{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2}};
static int x1,x2,y1,y2,n;
static boolean check(int x,int y){
if(x<0||x>=n||y<0||y>=n){
return false;
}
return true;
}
static int Bfs(){
Knight knight,kn;
while(!list.isEmpty()){
knight=list.removeFirst();
if(knight.x==x2&&knight.y==y2){
return knight.step;
}
for(int i=0;i0){
list.clear();
n=sc.nextInt();
x1=sc.nextInt();
y1=sc.nextInt();
x2=sc.nextInt();
y2=sc.nextInt();
for(int i=0;i