Aizu Online Judge 0122 Summer of Phyonkichi

■0122 Summer of Phyonkichi

適当にDFSをやって最後のスプリンクラーまでたどり着いたら"OK"．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int x, y;  
17.  int n;  
18.  int[] xs, ys;  
19.   
20.  // カエルのジャンプ範囲  
21.  int[] dx={-1, 0, 1, -1, 0, 1, -2, -2, -2, 2, 2, 2};  
22.  int[] dy={-2, -2, -2, 2, 2, 2, -1, 0, 1, -1, 0, 1};  
23.   
24.  void run(){  
25.   for(;;){  
26.    x=sc.nextInt();  
27.    y=sc.nextInt();  
28.    if((x|y)==0){  
29.     break;  
30.    }  
31.    n=sc.nextInt();  
32.    xs=new int[n];  
33.    ys=new int[n];  
34.    for(int i=0; i<n; i++){  
35.     xs[i]=sc.nextInt();  
36.     ys[i]=sc.nextInt();  
37.    }  
38.    solve();  
39.   }  
40.  }  
41.   
42.  void solve(){  
43.   for(int i=0; i<dx.length; i++){  
44.    if(dfs(x+dx[i], y+dy[i], 0)){  
45.     println("OK");  
46.     return;  
47.    }  
48.   }  
49.   println("NA");  
50.  }  
51.   
52.  // (x,y)にてk番目のスプリンクラーに突撃  
53.  boolean dfs(int x, int y, int k){  
54.   if(k==n){  
55.    return true;  
56.   }  
57.   if(x<0||x>=10||y<0||y>=10){  
58.    return false;  
59.   }  
60.   if(x<xs[k]-1||x>xs[k]+1||y<ys[k]-1||y>ys[k]+1){  
61.    return false;  
62.   }  
63.   for(int i=0; i<dx.length; i++){  
64.    if(dfs(x+dx[i], y+dy[i], k+1)){  
65.     return true;  
66.    }  
67.   }  
68.   return false;  
69.  }  
70.   
71.  void debug(Object... os){  
72.   System.err.println(Arrays.deepToString(os));  
73.  }  
74.   
75.  void print(String s){  
76.   System.out.print(s);  
77.  }  
78.   
79.  void println(String s){  
80.   System.out.println(s);  
81.  }  
82.   
83.  public static void main(String[] args){  
84.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
85.   new Main().run();  
86.  }  
87. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int x, y;
 int n;
 int[] xs, ys;

 // カエルのジャンプ範囲
 int[] dx={-1, 0, 1, -1, 0, 1, -2, -2, -2, 2, 2, 2};
 int[] dy={-2, -2, -2, 2, 2, 2, -1, 0, 1, -1, 0, 1};

 void run(){
  for(;;){
   x=sc.nextInt();
   y=sc.nextInt();
   if((x|y)==0){
    break;
   }
   n=sc.nextInt();
   xs=new int[n];
   ys=new int[n];
   for(int i=0; i<n; i++){
    xs[i]=sc.nextInt();
    ys[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  for(int i=0; i<dx.length; i++){
   if(dfs(x+dx[i], y+dy[i], 0)){
    println("OK");
    return;
   }
  }
  println("NA");
 }

 // (x,y)にてk番目のスプリンクラーに突撃
 boolean dfs(int x, int y, int k){
  if(k==n){
   return true;
  }
  if(x<0||x>=10||y<0||y>=10){
   return false;
  }
  if(x<xs[k]-1||x>xs[k]+1||y<ys[k]-1||y>ys[k]+1){
   return false;
  }
  for(int i=0; i<dx.length; i++){
   if(dfs(x+dx[i], y+dy[i], k+1)){
    return true;
   }
  }
  return false;
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}