ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1212 Mirror Illusion

・概要
問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1212

8x8の部屋に何枚かの鏡が設置されています。
(0.75, 0.25)の座標から(1, 0.5)の座標の方向を見たときに、壁または自分自身が見える座標を求める問題です。


・解法
シミュレーション問題です。

幾何っぽい感じはしますが、問題文を読むと視線は斜め(45度)なので鏡が視界に入っても入射角と反射角は変わりません。 だから幾何的な計算はなくても解くことができます。

下のコードはif文列挙しまくりであんまりよいコードではないような気がします。


ソースコード

#include<iostream>
#include<map>
#include<cstring>
using namespace std;

static const int dx[]={50,-50,-50,50};
static const int dy[]={50,50,-50,-50};
//{south_east, south_west, north_west, north_east}

int n;
bool mirror[9][9][9][9];

int main(){
  while(cin >> n){
    if(n < 0)break;
      
    memset(mirror,false,sizeof(mirror));
      
    for(int i = 0 ; i < n ; i++){
      char c;
      int px,py;
      cin >> c >> px >> py;
      if(c=='x'){
        mirror[px][py][px+1][py] = true;
      }
      if(c=='y'){
        mirror[px][py][px][py+1] = true;
      }
    }
      
    int x = 100;
    int y = 50;
    int dir = 0;
    bool ftime = true;
    bool stime = true;
    bool vertical = true;
    bool isMirror = false;
    while(true){
      //cout << "*** " << x << " " << y << " " << isMirror <<  endl;
      if(!stime){
        if(x==100 && y==50 && dir==0){
          x = 75;
          y = 25;
          break;
        }
        if((x==0 || y==0 || x==800 || y==800) && !isMirror)break;
      }
	 
      if(ftime) ftime = false;
      else{
        stime = false;
        x += dx[dir];
        y += dy[dir];
      }
      if(!vertical){
        vertical = true;
        if(dir==0){
          if(mirror[(x-50)/100][y/100][(x+50)/100][y/100]){
            dir = 3;
            isMirror = true;
          }
          else isMirror = false;
        }
        else if(dir==1){
          if(mirror[(x-50)/100][y/100][(x+50)/100][y/100]){
            dir = 2;
            isMirror = true;
          }
          else isMirror = false;
        }
        else if(dir==2){
          if(mirror[(x-50)/100][y/100][(x+50)/100][y/100]){
            dir = 1;
            isMirror = true;
          }
          else isMirror = false;
        }
        else{
          if(mirror[(x-50)/100][y/100][(x+50)/100][y/100]){
            dir = 0;
            isMirror = true;
          }
          else isMirror = false;
        }
      }
      else{
        vertical = false;
        if(dir==0){
          if(mirror[x/100][(y-50)/100][x/100][(y+50)/100]){
            dir = 1;
            isMirror = true;
          }
          else isMirror = false;
        }
        else if(dir==1){
          if(mirror[x/100][(y-50)/100][x/100][(y+50)/100]){
            dir = 0;
            isMirror = true;
          }
          else isMirror = false;
        }
        else if(dir==2){
          if(mirror[x/100][(y-50)/100][x/100][(y+50)/100]){
            dir = 3;
            isMirror = true;
          }
          else isMirror = false;
        }
        else{
          if(mirror[x/100][(y-50)/100][x/100][(y+50)/100]){
            dir = 2;
            isMirror = true;
          }
          else isMirror = false;
        }
      }
    }
      
    cout << x << " " << y << endl; 
  }
  return 0;
}