Div2 550, Div1 300 - RabbitStepping

SRM

問題概要

壁・既に行ったマス（以下壁で統一）に行くまで一直線に進むロボットがある。壁に当たると左へ方向転換する。東向きスタートとして、毎回曲がるまでに進んだマス数のログから長方形の部屋のサイズを推測せよ。

考え方

とりあえず、問題とは逆に部屋のサイズ (Width * Height) と、ロボットの初期位置が与えられればシミュレーションを作ること自体はそんなに難しくないだろう。データサイズも 50 x 50 程度に収まりそうなので。

それは一旦置いておいて、次はどうやって部屋のサイズを決めるのかを考える。とりあえず考えやすそうな、与えられたデータ数が少ない順番に考えてみる。
まずは値が 1 個の場合。サンプルデータ 1 にもある。これは解説もついている通り、1 * (moves[0] + 1) になるので難しくない。
次に値が 2 個の場合と 3 個の場合。2 個のデータはサンプルデータ 2 がある。とりあえず壁制限が無いものと思ってシミュレーションしてみて、その動く範囲を囲う形に部屋を設定すれば出来上がり。width に関しては右方向に進む moves[0] と 左方向に進む moves[2] があるので、大きい方を考慮するだけ。
そして本来のデータセットである 4 個以上の場合。とりあえず衝突する (return -1) かどうかは気にせず、3 個の場合と同じ要領で部屋サイズ、ロボットの初期位置を決めることは出来る。このサイズは、他のサイズになり得ない。なのであとはその設定に従ってシミュレーションしてみればいい。moves[i] 歩進むまでに壁を通過してたり、 moves[i] 歩進んだのに目の前が壁じゃないまま曲がったりしてるとアウト。

コード

#include <vector> 
#include <algorithm> 
using namespace std; 
bool dp[60][60]; 
struct RotatingBot { 

  int minArea(vector <int> moves) { 
    if (moves.size() == 1) return moves[0] + 1; 
    if (moves.size() == 2) return (moves[0] + 1) * (moves[1] + 1); 
    if (moves.size() == 3) return (max(moves[0], moves[2]) + 1) * (moves[1] + 1); 

    int height = max(moves[1], moves[3]) + 1;
    int width = max(moves[0], moves[2]) + 1;
    // 番兵の壁設置
    for (int i = 0; i <= height + 1; ++i) dp[0][i] = dp[width + 1][i] = true;
    for (int i = 0; i <= width + 1; ++i)  dp[i][0] = dp[i][height + 1] = true;
    const int DX[] = {1, 0, -1, 0}, DY[] = {0, -1, 0, 1};

    int x = width - moves[0], y = moves[1] + 1;
    dp[x][y] = true;  // index が (row, col) ではないのに注意
    for (int i = 0; i < moves.size(); ++i) {
      const int dx = DX[i % 4], dy = DY[i % 4];
      for (int j = 0; j < moves[i]; ++j) {
        x += dx; y += dy;
        if (dp[x][y]) return -1;  // 壁衝突判定
        dp[x][y] = true;
      }
      if (i < moves.size() - 1 && !dp[x + dx][y + dy]) return -1; 
    } 
    return height * width; 
  } 
};