Problem 1212 : Mirror Illusion

Problem E: Mirror Illusion
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1212

• 問題概要

グリッドな部屋に水平または垂直の鏡がいっぱい与えられて、初期位置から中心を見た場合最終的にはどこの壁をみていることになるか。もしくは、自分をみていることになるか。
その場所の座標を出力しなさい

• 解法

幾何とおもってはだめ。
右下右上左下左上にしか動けないことに注目。
９までの座標を４倍にして、鏡と自分の位置で方向がどうかわるかをテーブルにしたあと、
それをシュミュレーションするだけ。

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
#define vint       vector<int>
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define lli	    long long int
#define ld	    long double

#define N 33

using namespace std;

bool mx[N][N], my[N][N];
int tx[] = {1, -1, -1, 1}, ty[] = {1, 1, -1, -1},d, x, y;

int nd(){
  if(d == 0){
    if(y >= 2 && my[y-2][x])return 1;
    if(x >= 2 && mx[y][x-2])return 3;
  }
  if(d == 1){
    if(y >= 2 && my[y-2][x])return 0;
    if(x >= 2 && mx[y][x-2])return 2;
  }
  if(d == 2){
    if(y >= 2 && my[y-2][x])return 3;
    if(x >= 2 && mx[y][x-2])return 1;
  }
  if(d == 3){
    if(y >= 2 && my[y-2][x])return 2;
    if(x >= 2 && mx[y][x-2])return 0;
  }
  return d;
}

void reset(){
  rep(i, N)rep(j, N)mx[i][j] = my[i][j] = false;
  x = 3;
  y = 1;
  d = 0;
}

bool end(){
  if(x < 0 || y < 0 || x >= N || y >= N){
    x -= tx[d];
    y -= ty[d];
    return true;
  }
  if(x == 3 && y == 1)return true;
  return false;
}



main(){
  int n;
  while(cin >>n ){
    if(n < 0)break;
    reset();
    rep(i, n){
      int tx, ty;
      char c;
      cin >> c >> tx >> ty;
      if(c == 'x')mx[ty*4][tx*4] = true;
      if(c == 'y')my[ty*4][tx*4] = true;
    }
    x += tx[d];
    y += ty[d];
    while(!end()){
      d = nd();
      x += tx[d];
      y += ty[d];
    }
    cout << x * 100 / 4 << ' ' << y * 100 / 4 << endl;
  }
}