SRM611 Div2 Hard "ElephantDrinkingEasy"
問題
TopCoder Statistics - Problem Statement
訳
N * Nのグリッド状のマスで構成されたフィールドがある。いくつかのマスは水場となっている。あなたはフィールドの状態を表したString[] fieldが与えられる。field[i][j]が'Y'であれば、マス(i, j)は水場であり、'N'であればそうでないことを表す。
下図の緑色の部分が表すように、フィールドを囲うようにして4 * Nの象がいる。1つのマスには一頭の象がいる。象は鼻で水を飲むことができる。それぞれの象はフィールドに対し、まっすぐ伸ばした鼻のみ入ることができる。なので、フィールドの左側にいる象は鼻を右に伸ばすことになる。鼻は、フィールドの端から端まで伸ばすことができる。
さらに制限があり、象の鼻が交差することはできない。それぞれの水場は、一頭の象しか利用できない。
例えば、図の(a)は制限を満たしている。水場は青、象は緑、象の鼻は赤である。ここでは4頭の象が水を飲んでいる。図の(b), (c)は制限を満たしていない。両方とも鼻が交差してしまっている。
課題は、同時に水を飲むことができる像の数の最大値を求めることである。
制約
2 <= N <= 5
考えたこと
像の数は最大でも5 * 4の20頭。それぞれの象が飲む・飲まないの状態があるが、2^20 = 3000万ぐらいなので、シミュレートでいける。
実装方法として、N頭ごとにフィールドを90度回転させてやると楽かもしれない。
ソースコード
int N; class ElephantDrinkingEasy { public: // 90度回転させる vector <string> rotate(vector <string> M) { vector<string> res; for (int y = 0; y < N; y++) { res.push_back(""); for (int x = 0; x < N; x++) { int sy = N - 1 - x; int sx = y; res[y] += M[sy][sx]; } } return res; } int dfs(int i, vector <string> M) { if (i == N * 4) { return 0; } // N頭ごとにフィールドを90度回転 if (i % N == 0) { M = rotate(M); } // 吸わない int res = dfs(i + 1, M); // 吸う int x = i % N; for (int y = 0; y < N; y++) { // 水を見つけた if (M[y][x] == 'Y') { for (int yy = 0; yy <= y; yy++) M[yy][x] = 'X'; res = max(res, dfs(i + 1, M) + 1); } if (M[y][x] == 'X') break; } return res; } int maxElephants(vector <string> map) { N = map.size(); return dfs(0, map); } };