TopCoder 練習 KnightsTour(SRM 447 Div1 Easy)

KnightsTour(SRM 447 Div1 Easy)

■問題
本家参照．

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

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3.   
4. public class KnightsTour{  
5.  int[] dx={1,-1,2,-2,2,-2,1,-1};  
6.  int[] dy={2,2,1,1,-1,-1,-2,-2};  
7.  public int visitedPositions(String[] ss){  
8.   boolean[][] visited=new boolean[8][8];  
9.   int x=0,y=0;  
10.   for(int j=0;j<8;j++){  
11.    for(int i=0;i<8;i++){  
12.     if(ss[j].charAt(i)=='K'){  
13.      x=i;  
14.      y=j;  
15.     }  
16.    }  
17.   }  
18.   visited[y][x]=true;  
19.   int[] num=new int[8];  
20.   for(int c=1;;c++){  
21.    Arrays.fill(num,9);  
22.    for(int j=0;j<8;j++){  
23.     int nx=x+dx[j];  
24.     int ny=y+dy[j];  
25.     if(nx<0||nx>=8||ny<0||ny>=8||visited[ny][nx]||ss[ny].charAt(nx)=='*'){  
26.      continue;  
27.     }  
28.     num[j]=0;  
29.     visited[ny][nx]=true;  
30.     for(int i=0;i<8;i++){   
31.      int nnx=nx+dx[i];  
32.      int nny=ny+dy[i];  
33.      if(nnx<0||nnx>=8||nny<0||nny>=8||visited[nny][nnx]||ss[nny].charAt(nnx)=='*'){  
34.       continue;  
35.      }  
36.      num[j]++;  
37.     }  
38.     visited[ny][nx]=false;  
39.    }  
40.    int k=0;  
41.    for(int i=0;i<8;i++){  
42.     if(num[i]<=num[k]){  
43.      k=i;  
44.     }  
45.    }  
46.    if(num[k]>8){  
47.     return c;  
48.    }  
49.    x+=dx[k];  
50.    y+=dy[k];  
51.    visited[y][x]=true;  
52.    // System.out.println(x+","+y);  
53.    // System.out.println("num["+k+"]="+num[k]);  
54.   }  
55.  }  
56. }  

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