Aizu Online Judge 0207 Block

■0207 Block

(xs,ys)から同じ色を持つブロックについてBFS．(xg,yg)が訪問済みであれば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 w, h;  
17.  int sx, sy;  
18.  int gx, gy;  
19.  int[][] a;  
20.   
21.  void run(){  
22.   for(;;){  
23.    w=sc.nextInt();  
24.    h=sc.nextInt();  
25.    if((w|h)==0){  
26.     break;  
27.    }  
28.    sx=sc.nextInt()-1;  
29.    sy=sc.nextInt()-1;  
30.    gx=sc.nextInt()-1;  
31.    gy=sc.nextInt()-1;  
32.    int n=sc.nextInt();  
33.    a=new int[h][w];  
34.    for(int k=0; k<n; k++){  
35.     int c=sc.nextInt();  
36.     int d=sc.nextInt();  
37.     int x=sc.nextInt()-1;  
38.     int y=sc.nextInt()-1;  
39.     for(int j=0; j<2; j++){  
40.      for(int i=0; i<4; i++){  
41.       if(d==0){  
42.        a[y+j][x+i]=c;  
43.       }else{  
44.        a[y+i][x+j]=c;  
45.       }  
46.      }  
47.     }  
48.    }  
49.    solve();  
50.   }  
51.  }  
52.   
53.  void solve(){  
54.   LinkedList<P> que=new LinkedList<P>();  
55.   boolean[][] visited=new boolean[h][w];  
56.   
57.   int[] dx={0, 0, -1, 1};  
58.   int[] dy={-1, 1, 0, 0};  
59.   
60.   que.offer(new P(sx, sy));  
61.   visited[sy][sx]=true;  
62.   
63.   for(; !que.isEmpty();){  
64.    P p=que.poll();  
65.    for(int i=0; i<4; i++){  
66.     P q=new P(p.x+dx[i], p.y+dy[i]);  
67.     if(q.x>=0&&q.x<w&&q.y>=0&&q.y<h&&a[q.y][q.x]==a[sy][sx]  
68.       &&!visited[q.y][q.x]){  
69.      que.offer(q);  
70.      visited[q.y][q.x]=true;  
71.     }  
72.    }  
73.   }  
74.   println(visited[gy][gx]?"OK":"NG");  
75.  }  
76.   
77.  class P{  
78.   int x, y;  
79.   
80.   P(int x, int y){  
81.    this.x=x;  
82.    this.y=y;  
83.   }  
84.  }  
85.   
86.  void debug(Object... os){  
87.   System.err.println(Arrays.deepToString(os));  
88.  }  
89.   
90.  void print(String s){  
91.   System.out.print(s);  
92.  }  
93.   
94.  void println(String s){  
95.   System.out.println(s);  
96.  }  
97.   
98.  public static void main(String[] args){  
99.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
100.   new Main().run();  
101.  }  
102. }  

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 w, h;
 int sx, sy;
 int gx, gy;
 int[][] a;

 void run(){
  for(;;){
   w=sc.nextInt();
   h=sc.nextInt();
   if((w|h)==0){
    break;
   }
   sx=sc.nextInt()-1;
   sy=sc.nextInt()-1;
   gx=sc.nextInt()-1;
   gy=sc.nextInt()-1;
   int n=sc.nextInt();
   a=new int[h][w];
   for(int k=0; k<n; k++){
    int c=sc.nextInt();
    int d=sc.nextInt();
    int x=sc.nextInt()-1;
    int y=sc.nextInt()-1;
    for(int j=0; j<2; j++){
     for(int i=0; i<4; i++){
      if(d==0){
       a[y+j][x+i]=c;
      }else{
       a[y+i][x+j]=c;
      }
     }
    }
   }
   solve();
  }
 }

 void solve(){
  LinkedList<P> que=new LinkedList<P>();
  boolean[][] visited=new boolean[h][w];

  int[] dx={0, 0, -1, 1};
  int[] dy={-1, 1, 0, 0};

  que.offer(new P(sx, sy));
  visited[sy][sx]=true;

  for(; !que.isEmpty();){
   P p=que.poll();
   for(int i=0; i<4; i++){
    P q=new P(p.x+dx[i], p.y+dy[i]);
    if(q.x>=0&&q.x<w&&q.y>=0&&q.y<h&&a[q.y][q.x]==a[sy][sx]
      &&!visited[q.y][q.x]){
     que.offer(q);
     visited[q.y][q.x]=true;
    }
   }
  }
  println(visited[gy][gx]?"OK":"NG");
 }

 class P{
  int x, y;

  P(int x, int y){
   this.x=x;
   this.y=y;
  }
 }

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