torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder Single Round Match 566, Division 2, Level 1 : PenguinTiles

概要

全く同じ絵柄が印字されたいくつかの正方形のパネルからなるスライドパズルがある。
一度に一つのパネルを動かして(押されたパネルが動いて複数動くことはある)、右下を空きマスにしたい。
必要な操作の回数を求めよ。

解法

空きマスの場所によって場合分けできます。

  • 空きマスが右下→0
  • 空きマスが右端の列か一番下の行→1
  • それ以外→2

従って、盤面を前探索し、空きマスを見つけた場所によって答えを返します。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class PenguinTiles
{
public:
	int minMoves( vector <string> tiles )
	{
		const int H = tiles.size(), W = tiles[0].size();

		REP( i, 0, H )
		{
			REP( j, 0, W )
			{
				if ( tiles[i][j] == 'P' )
				{
					continue;
				}
	
				if ( i + 1 == H && j + 1 == W )
				{
					return 0;
				}
				else if ( i + 1 == H || j + 1 == W )
				{
					return 1;
				}
				else
				{
					return 2;
				}
			}
		}

		return -1;
	}
};