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]);
  }
 }
}