AOJ 0209 Scene in a Picture

問題

日本語なので特に説明はないです。何故、数ヶ月にWAだしたのか分からない問題、放置してた。

解法

切れ端を90度ずつ回転させたのを配列に入れておいて、全探索。 O(4n²m²)ぐらいかなと思ってたけど以外に速く終わった。

コード

int pic[100][100];
int piece[4][50][50];
int n, m;

bool ck(int sy, int sx, int d){
  rep(i, m) rep(j, m){
    if(piece[d][i][j] == -1) continue;
    if(pic[sy+i][sx+j] != piece[d][i][j]) return false;
  }
  return true;
}

int main(){
  while(scanf("%d%d", &n, &m) && n+m){
    rep(i, n) rep(j, n) scanf("%d", &pic[i][j]);
    rep(i, m) rep(j, m) scanf("%d", &piece[0][i][j]);
    REP(k, 1, 4){
      rep(i, m) rep(j, m) piece[k][j][m-i-1] = piece[k-1][i][j];
    }

    rep(i, n-m+1) rep(j, n-m+1) rep(k, 4){
      if(ck(i, j, k)){
    rep(l, m) rep(h, m) if(piece[k][l][h] != -1){
      printf("%d %d\n", j+h+1, i+l+1);
      goto end;
    }
      }
    }
    puts("NA");
  end:;
  }
  return 0;
}