2013年1月4日

UVa 466 - Mirror, Mirror


#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <map>

using namespace std;

void rotate(vector<string>& v) {
  int r, c, n = v.size();
  vector<string> temp = v;
  for (r = 0; r < n; r++)
    for (c = 0; c < n; c++)
      temp[c][n - r - 1] = v[r][c];
  v = temp;
}

void reflect(vector<string>& v) {
  int r, c, n = v.size();
  vector<string> temp = v;
  for (r = 0; r < n; r++)
    for (c = 0; c < n; c++)
      temp[r][c] = v[n - r - 1][c];
  v = temp;
}

int main() {
  int n, C = 1;
  while (cin >> n) {
    vector<string> source, end;
    while (n--) {
      string a, b;
      cin >> a >> b;
      source.push_back(a);
      end.push_back(b);
    }
    printf("Pattern %d was ", C++);
    queue<vector<string> > q;
    map<vector<string>, int> path;
    path[source] = 0;
    q.push(source);
    bool found = 0;
    while (!q.empty()) {
      vector<string> now = q.front();
      q.pop();
      int len = path[now];
      if (now == end) {
        if (!len) puts("preserved.");
        else if (len < 4) printf("rotated %d degrees.\n", len * 90);
        else if (len == 10) puts("reflected vertically.");
        else printf("reflected vertically and rotated %d degrees.\n", ((4 - len % 10) % 4) * 90);
        found = 1;
        break;
      }
      for (int r = 1; r <= 4; r++) {
        rotate(now);
        if (!path.count(now)) {
          q.push(now);
          path[now] = len + r;
        }
        reflect(now);
        if (!path.count(now)) {
          q.push(now);
          path[now] = len + (r % 4) + 10;
        }
        reflect(now);
      }
    }
    if (!found) puts("improperly transformed.");
  }
  return 0;
}

沒有留言:

張貼留言