土下座しながら探索中

主に競技プログラミング

AOJ 0037 : Path on a Grid

問題リンク:格子状の経路 | Aizu Online Judge

解法:
問題で言われている通りに書く
自分は最初にcharの2次元配列に壁や床を書き、スタート地点から人を動かしていった
dx = {+1,+0,-1,+0};
dy
= {+0,+1,+0,-1};
という配列を用意して、最初の時点では0の方向を見ているものとした
ここから、もし手が壁から離れたならば今見ている方向に+1した方向へ変更し、
進んだ先が壁だったなら今見ている方向に-1した方向へ変更した

コード:

#include<iostream>
#include<cassert>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)
#define MAX 100 
using namespace std;

struct You
{//手の位置は自分の座標にdx[(dir+1)%4],dy[(dir+1)%4]を加えた場所
  int x,y,dir;
  You(int x=-inf,int y=-inf):x(x),y(y),dir(0){}
};

char G[MAX][MAX];
int dx[] = {+1,+0,-1,+0};
int dy[] = {+0,+1,+0,-1};

void init()
{
  rep(i,MAX)rep(j,MAX)G[i][j] = '.';
}

void makeGraph()
{
  string line;
  int x;
  REP(y,1,10)
    {//odd -> yoko, even -> tate
      cin >> line;
      x = (y%2?1:0);
      rep(i,line.size())
	{
	  if(line[i] == '1')
	    {
	      G[y][x] = (y%2?'-':'|');
	      if(y%2) G[y][x-1] = G[y][x+1] = 'o';
	      else    G[y+1][x] = G[y-1][x] = 'o';
	    }
	  x += 2;
	}
    }
}

void print()
{
  rep(i,11)
    {
      rep(j,11)
	{
	  cout << G[i][j];
	}
      cout << endl;
    }
  cout << endl;
}

void compute()
{
  You you(0,0);
  bool fir = true;
  while(true)
    {
      int x = you.x,y = you.y,dir = you.dir;
      int hx = x + dx[(dir+1)%4],hy = y + dy[(dir+1)%4];
      if(!fir && hx == 0 && hy == 1)
	{
	  cout << '\n';
	  return;
	}
      fir = false;

      int nx = x + dx[dir],ny = y + dy[dir];
      hx += dx[dir],hy += dy[dir];
      assert(G[ny][nx] != 'o');

      if(G[ny][nx] == '|' || G[ny][nx] == '-')
	{
	  dir = (dir + 3)%4;
	  you.dir = dir;
	}
      else if(G[hy][hx] == '.')
	{
	  dir = (dir + 1)%4;
	  you.x = nx + dx[dir], you.y = ny + dy[dir],you.dir = dir;	  
	}
      else if(G[hy][hx] == 'o' || G[hy][hx] == '-' || G[hy][hx] == '|')
	{
	  you.x += dx[dir],you.y += dy[dir];
	}

      hx = you.x + dx[(dir+1)%4], hy = you.y + dy[(dir+1)%4];

      if(G[hy][hx] != 'o')
	cout << (dir==0?'R':(dir==1?'D':(dir==2?'L':'U')));
    }
}

int main()
{
  init();
  makeGraph();
  compute();
  return 0;
}