1915 Knight Moves

「1915 Knight Moves」の編集履歴(バックアップ)一覧はこちら

1915 Knight Moves」(2006/04/17 (月) 01:50:05) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**1915 Knight Moves **問題 http://acm.pku.edu.cn/JudgeOnline/problem?id=1915 **解答方針 BFS. **解答例 import java.util.*; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for(int i=0;i<n;i++){ int size = sc.nextInt(); int sx = sc.nextInt(); int sy = sc.nextInt(); int ex = sc.nextInt(); int ey = sc.nextInt(); Solver sol = new Solver(size,sx,sy,ex,ey); System.out.println(sol.solve()); } } } class Solver{ int size; int startx; int starty; int endx; int endy; Solver(int s,int x1,int y1,int x2,int y2){ size = s; startx = x1; starty = y1; endx = x2; endy = y2; } public int solve(){ Queue<Point> q = new LinkedList<Point>(); boolean table[][] = new boolean[size][size]; for(int i=0;i<size;i++) for(int j=0;j<size;j++) table[i][j] = true; q.offer(new Point(startx,starty,(int)0)); table[startx][starty] = false; while(true){ Point p = q.poll(); if(p.x==endx&&p.y==endy){ return p.turn; } Point newpoints[] = new Point[8]; newpoints[0] = new Point(p.x+1,p.y+2,p.turn+1); newpoints[1] = new Point(p.x+2,p.y+1,p.turn+1); newpoints[2] = new Point(p.x-1,p.y+2,p.turn+1); newpoints[3] = new Point(p.x-2,p.y+1,p.turn+1); newpoints[4] = new Point(p.x-1,p.y-2,p.turn+1); newpoints[5] = new Point(p.x-2,p.y-1,p.turn+1); newpoints[6] = new Point(p.x+1,p.y-2,p.turn+1); newpoints[7] = new Point(p.x+2,p.y-1,p.turn+1); for(int i=0;i<8;i++){ if(newpoints[i].check(size)&&table[newpoints[i].x][newpoints[i].y]){ q.offer(newpoints[i]); table[newpoints[i].x][newpoints[i].y]=false; } } } } } class Point{ int x; int y; int turn; Point(int ix,int iy,int t){ x = ix; y = iy; turn = t; } public boolean check(int size){ if(0<=x&&x<size&&0<=y&&y<size) return true; else return false; } }

表示オプション

横に並べて表示:
変化行の前後のみ表示:
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。