AOJ0037

問題:Path on a Grid
グリッド上の壁情報を与えられ，初期位置から右手づたいに進んでいき，初期位置まで帰ってくるまでの移動方向を出力する問題．
壁情報を配列で扱いやすいよう整理し，それをたどればOK.

自分はサンプル入力の

1111
00001
0110
01011
0010
01111
0010
01001
0111

これを

00000000000
01111111110
00000000010
00011111010
00010001010
00010111010
00010101010
00010111010
00010000010
00011111110
00000000000

のようにして配列に格納しています.

#include<iostream>
#include<string>
#include<vector>
using namespace std;

static const int X = 11;
static const int Y = 11;
static const int DIR = 4;
static const string dirchar= "RDLU";
static const int dirx[DIR] = {1,0,-1,0};
static const int diry[DIR] = {0,1,0,-1};


int main()
{
	int field[X][Y] = {0};
	string s;
	int x,y;
	y=0;
	while( getline(cin,s) )
	{
		for(x=0;x<s.size();++x)
		{
			field[x*2+1][y+1] = s[x]-'0';
		}
		y++;
	}
	//横情報を右に引き延ばし
	for(y=1;y<Y;y+=2)
	{
		for(x=1;x<X;x+=2)
		{
			if(field[x][y])
			{
				field[x+1][y] = 1;
			}
		}
	}
	//縦情報を上下に引き延ばし
	for(y=2;y<Y;y+=2)
	{
		for(x=1;x<X;x+=2)
		{
			if(field[x][y])
			{
				field[x][y+1] = 1;
				field[x][y-1] = 1;
			}
		}
	}
	//field上の１をたどっていく
	vector<int> ans;
	x=y=1;
	int dir=0;
	while(true)
	{
		for(int i=0; i<DIR; ++i)
		{
			const int tdir = (dir+DIR-1+i)%DIR;
			if( field[x + dirx[tdir]][y + diry[tdir]] )
			{
				//fieldを2倍に引き延ばしてるので2マスずつ移動
				x += dirx[tdir]*2;
				y += diry[tdir]*2;
				ans.push_back(tdir);
				dir = tdir;
				break;
			}
		}
		if( x==1 && y==1 )break;
	}
	//解答出力
	for(int i=0;i<ans.size();++i)
	{
		cout << dirchar[ans[i]];
	}cout << endl;
	return 0;
}