写真に写っている景色は？

パソコン甲子園2009 問題05 写真に写っている景色は？

問題文

数字が書かれたn×n個のマスから成るグリッドにおいて、同じく数字が書かれたm×m個のマスから成るグリッドを0, 90, 180, または270度回転させたパタンに一致する領域を探し、その位置を出力する問題です。

m×mのグリッドを回転しながら、全ての場所について一致しているかを調べていきます。n×nのグリッドにおけるm×mの領域について、上から下、左から右の順番で調べていきます。各領域について、m×mのグリッドを回転させ、重なった部分のマスが全て一致するか（問題の仕様上-1は無視します）をチェックします。

#include<iostream>
using namespace std;
#define rep(i, n) for ( int i = 0; i < (int)n; i++ )
#define NMAX 200
#define MMAX 100
#define INFTY (1<<21)
int n, m, T[NMAX][NMAX], P[MMAX][MMAX];

void valid(int sx, int sy, int &lx, int &ly ){
    int ax = -1, ay;
    rep(y, m) rep(x, m){
	if ( P[x][y] == -1 ) continue;
	if ( P[x][y] != T[sx+x][sy+y] ) return;
	if ( ax == -1 ) {ay = y; ax = x;}
    }
    if ( ay < ly || (ay == ly && ax < lx) ) {ly = sy+ay; lx = sx+ax; }
}

bool rotate(int sx, int sy){
    int tmp[MMAX][MMAX];
    int ly = INFTY, lx;
    rep(r, 4){
	valid(sx, sy, lx, ly);
	rep(y, m) rep(x, m) tmp[x][y] = P[x][y];
	rep(y, m) rep(x, m) P[y][m-x-1] = tmp[x][y];
    }
    if ( ly == INFTY ) return false;
    cout << lx+1 << " " << ly+1 << endl;
    return true;
}

void compute(){
    rep(y, n-m+1) rep(x, n-m+1) if ( rotate(x, y) ) return;
    cout << "NA" << endl;
}

main(){
    while( cin >> n >> m && n ){
	rep(y, n) rep(x, n) cin >> T[x][y];
	rep(y, m) rep(x, m) cin >> P[x][y];
	compute();
    }
}