Aizu Online Judge 0209 Scene in a Picture

■0209 Scene in a Picture

全探索．

計算量はO(m²n²)だが，100²50²=2.5*10⁷なので余裕．

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 m, n;  
17.  int[][] a, b;  
18.   
19.  void run(){  
20.   for(;;){  
21.    m=sc.nextInt();  
22.    n=sc.nextInt();  
23.    if((m|n)==0){  
24.     break;  
25.    }  
26.    a=new int[m][m];  
27.    b=new int[n][n];  
28.    for(int j=0; j<m; j++){  
29.     for(int i=0; i<m; i++){  
30.      a[j][i]=sc.nextInt();  
31.     }  
32.    }  
33.    for(int j=0; j<n; j++){  
34.     for(int i=0; i<n; i++){  
35.      b[j][i]=sc.nextInt();  
36.     }  
37.    }  
38.    solve();  
39.   }  
40.  }  
41.   
42.  void solve(){  
43.   int[][][] c=new int[4][n][n];  
44.   for(int j=0; j<n; j++){  
45.    for(int i=0; i<n; i++){  
46.     c[0][j][i]=b[j][i];  
47.     c[1][i][n-1-j]=b[j][i];  
48.     c[2][n-1-j][n-1-i]=b[j][i];  
49.     c[3][n-1-i][j]=b[j][i];  
50.    }  
51.   }  
52.   
53.   int p=m*m;  
54.   for(int i=0; i<4; i++){  
55.    p=min(p, match(c[i]));  
56.   }  
57.   if(p==m*m){  
58.    println("NA");  
59.   }else{  
60.    println((p%m+1)+" "+(p/m+1));  
61.   }  
62.  }  
63.   
64.  int match(int[][] c){  
65.   for(int y=0; y+n<=m; y++){  
66.    for(int x=0; x+n<=m; x++){  
67.     boolean f=true;  
68.     for(int j=0; j<n; j++){  
69.      for(int i=0; i<n; i++){  
70.       f&=c[j][i]==-1||c[j][i]==a[y+j][x+i];  
71.      }  
72.     }  
73.     if(f){  
74.      for(int j=0; j<n; j++){  
75.       for(int i=0; i<n; i++){  
76.        if(c[j][i]!=-1){  
77.         return (y+j)*m+(x+i);  
78.        }  
79.       }  
80.      }  
81.     }  
82.    }  
83.   }  
84.   return m*m;  
85.  }  
86.   
87.  void debug(Object... os){  
88.   System.err.println(Arrays.deepToString(os));  
89.  }  
90.   
91.  void print(String s){  
92.   System.out.print(s);  
93.  }  
94.   
95.  void println(String s){  
96.   System.out.println(s);  
97.  }  
98.   
99.  public static void main(String[] args){  
100.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
101.   new Main().run();  
102.  }  
103. }  

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 m, n;
 int[][] a, b;

 void run(){
  for(;;){
   m=sc.nextInt();
   n=sc.nextInt();
   if((m|n)==0){
    break;
   }
   a=new int[m][m];
   b=new int[n][n];
   for(int j=0; j<m; j++){
    for(int i=0; i<m; i++){
     a[j][i]=sc.nextInt();
    }
   }
   for(int j=0; j<n; j++){
    for(int i=0; i<n; i++){
     b[j][i]=sc.nextInt();
    }
   }
   solve();
  }
 }

 void solve(){
  int[][][] c=new int[4][n][n];
  for(int j=0; j<n; j++){
   for(int i=0; i<n; i++){
    c[0][j][i]=b[j][i];
    c[1][i][n-1-j]=b[j][i];
    c[2][n-1-j][n-1-i]=b[j][i];
    c[3][n-1-i][j]=b[j][i];
   }
  }

  int p=m*m;
  for(int i=0; i<4; i++){
   p=min(p, match(c[i]));
  }
  if(p==m*m){
   println("NA");
  }else{
   println((p%m+1)+" "+(p/m+1));
  }
 }

 int match(int[][] c){
  for(int y=0; y+n<=m; y++){
   for(int x=0; x+n<=m; x++){
    boolean f=true;
    for(int j=0; j<n; j++){
     for(int i=0; i<n; i++){
      f&=c[j][i]==-1||c[j][i]==a[y+j][x+i];
     }
    }
    if(f){
     for(int j=0; j<n; j++){
      for(int i=0; i<n; i++){
       if(c[j][i]!=-1){
        return (y+j)*m+(x+i);
       }
      }
     }
    }
   }
  }
  return m*m;
 }

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