2010年11月20日土曜日

TopCoder 練習 KnightsTour(SRM 447 Div1 Easy)

KnightsTour(SRM 447 Div1 Easy)

■問題
本家参照.

■解法
組むだけ.特に高速化の必要もありませんでした.

import java.util.*;
import java.lang.*;

public class KnightsTour{
int[] dx={1,-1,2,-2,2,-2,1,-1};
int[] dy={2,2,1,1,-1,-1,-2,-2};
public int visitedPositions(String[] ss){
boolean[][] visited=new boolean[8][8];
int x=0,y=0;
for(int j=0;j<8;j++){
for(int i=0;i<8;i++){
if(ss[j].charAt(i)=='K'){
x=i;
y=j;
}
}
}
visited[y][x]=true;
int[] num=new int[8];
for(int c=1;;c++){
Arrays.fill(num,9);
for(int j=0;j<8;j++){
int nx=x+dx[j];
int ny=y+dy[j];
if(nx<0||nx>=8||ny<0||ny>=8||visited[ny][nx]||ss[ny].charAt(nx)=='*'){
continue;
}
num[j]=0;
visited[ny][nx]=true;
for(int i=0;i<8;i++){
int nnx=nx+dx[i];
int nny=ny+dy[i];
if(nnx<0||nnx>=8||nny<0||nny>=8||visited[nny][nnx]||ss[nny].charAt(nnx)=='*'){
continue;
}
num[j]++;
}
visited[ny][nx]=false;
}
int k=0;
for(int i=0;i<8;i++){
if(num[i]<=num[k]){
k=i;
}
}
if(num[k]>8){
return c;
}
x+=dx[k];
y+=dy[k];
visited[y][x]=true;
// System.out.println(x+","+y);
// System.out.println("num["+k+"]="+num[k]);
}
}
}

0 件のコメント: