TopCoder Marathon Match 78 : FixTheFence

方針とか

最初に書いたコードは、「ランダムに長方形をプロットして、一番ましなやつを出力」でした。
主な目的は出力形式の確認ですかね……。

二番目に書いた（そして最終である）コードは、盤面をジグザグに辿りながら、2 と 3 の横を通るときに適当に曲がって充足させるものです。
画像で見た方が早いと思うので以下を参照。

では、以下汚いコードの品評会です。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;
typedef istringstream ISS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

#define MP( a, b ) make_pair( ( a ), ( b ) )

#define fst first
#define snd second

const char dirchar[] = "DURL";
map<char,PII> dir;

class FixTheFence
{
public:
	int sz;
	VS board;

	string findLoop( vector<string> board )
	{
		sz = board.size();
		this -> board = board;

		dir['D'] = MP( 1, 0 );
		dir['U'] = MP( -1, 0 );
		dir['R'] = MP( 0, 1 );
		dir['L'] = MP( 0, -1 );

		vector< VS > guides( sz + 1, VS( sz + 1 ) );

		REP( i, 0, sz + 1 )
		{
			fill( ALL( guides[i] ), i % 4 < 2 ? 'R' : 'L' );
			guides[i][0] = 'U';
			guides[i][1] = 'U';
		}

		for ( int i = 0; i < sz; i += 2 )
		{
			REP( j, 2, sz )
			{
				switch ( i % 4 )
				{
					case 0:
						switch ( board[i][j] )
						{
							case '2':
								guides[i][j] = "RDR";
								guides[ i + 1 ][j] = "RUR";
								break;
							case '3':
								guides[i][j] = "DRUR";
								guides[ i + 1 ][j] = "URDR";
								guides[i][ j + 1 ] = "DR";
								guides[ i + 1 ][ j + 1 ] = "UR";
								break;
						}
						break;
					case 2:
						switch ( board[i][j] )
						{
							case '2':
								guides[i][ j + 1 ] = "LDL";
								guides[ i + 1 ][ j + 1 ] = "LUL";
								break;
							case '3':
								guides[i][ j + 1 ] = "DLUL";
								guides[ i + 1 ][ j + 1 ] = "ULDL";
								if ( guides[i][j] == "L" )
								{
									guides[i][j] = "DL";
									guides[ i + 1 ][j] = "UL";
								}
								break;
						}
						break;
				}
			}
		}

		REP( i, 0, sz )
		{
			switch ( board[i][0] )
			{
				case '2':
					guides[ i + 1 ][0] = "URU";
					guides[ i + 1 ][1] = "ULU";
					break;
				case '3':
					guides[ i + 1 ][0] = "RULU";
					guides[ i + 1 ][1] = "LURU";
					guides[i][0] = "RU";
					guides[i][1] = "LU";
			}
		}

		int y = 0, x = 2;
		string res( "0 0 RR" );

		while ( y + 4 <= sz )
		{
			while ( true )
			{
				PII d = diffCoordinate( guides[y][x] );
				int dy = y + d.fst, dx = x + d.snd;

				if ( inside( dy, dx ) )
				{
					res += guides[y][x];
					y = dy;
					x = dx;
				}
				else
				{
					break;
				}
			}

			while ( y % 4 != 2 )
			{
				y++;
				res += 'D';
			}

			while ( true )
			{
				PII d = diffCoordinate( guides[y][x] );
				int dy = y + d.fst, dx = x + d.snd;
			
				if ( inside( dy, dx ) )
				{
					res += guides[y][x];
					y = dy;
					x = dx;
				}
				else
				{
					break;
				}
			}

			while ( y % 4 )
			{
				y++;
				res += 'D';
			}
		}

		res += string( x - 1, 'L' );
		x = 1;

		while ( true )
		{
			PII d = diffCoordinate( guides[y][x] );
			int dy = y + d.fst, dx = x + d.snd;

			if ( 0 <= dy && dy < sz + 1 && 0 <= x && x < sz + 1 )
			{
				res += guides[y][x];
				y = dy;
				x = dx;
			}
			else
			{
				break;
			}
		}

		res += string( y, 'U' );
		if ( x )
		{
			res[2] = '1';
			res.erase( 5, 1 );
		}
		return res;
	}

	PII diffCoordinate( string guide )
	{
		int y = 0, x = 0;
		REP( i, 0, guide.size() )
		{
			PII d = dir[ guide[i] ];
			y += d.fst;
			x += d.snd;
		}
		return MP( y, x );
	}

	bool inside( int y, int x )
	{
		return 0 <= y && y < sz + 1 && 2 <= x && x < sz + 1;
	}

	void dumpResult( string str )
	{
		int y, x;
		string walk;
		ISS( str ) >> y >> x >> walk;

		VVI visited( sz + 1, VI( sz + 1, 0 ) );
		REP( i, 0, walk.size() )
		{
			visited[y][x] ++;
			
			PII d = dir[ walk[i] ];
			y += d.fst;
			x += d.snd;
		}

		REP( i, 0, visited.size() )
		{
			REP( j, 0, visited[i].size() )
			{
				if ( 2 <= visited[i][j] )
				{
					cout << "visited twice at ( " << i << ", " << j << " ) ." << endl;
				}
			}
		}

		return;
	}
};