右折 [Mujin Programming Challenge 2018 C]

https://beta.atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_c

考察過程

1. 制約からO(NM)かなと思う
2. 移動が1回だけでまずは考えてみる。これはDPできそう。dp[y][x] := 1回目で(x,y)に止まる始点の組み合わせ数
3. 2回目の移動もDPできないかと考える
4. 1回目の移動のDPを使えばできそう。dp2[y][x] := 2回目で(x,y)に止まる始点の組み合わせ数
5. あとは、実装が大変という問題があるが、4方向あるのでdxdyが使えないか考える
6. 使えるのでそれで実装しよう

解説

https://beta.atcoder.jp/contests/mujin-pc-2018/submissions/2947241

dp(x,y,d) := d方向から来て終点が(x,y)である1回目の移動の組み合わせ数
dp2(x,y,d) := d方向から来て終点が(x,y)である2回目の移動の組み合わせ数
これを計算する。
方向によってDPしていく向きが変わるので、メモ化再帰をするのがオススメ。
最終的にdp2(x,y,d)の総和をとると答え。
　
dp(x,y,d)を考えよう。
(x,y)からd移動した先を(xx,yy)とする。
すると、dp(x,y,d) = dp(xx,yy,d)+1となる。
dp(xx,yy,d)は(xx,yy)から1つ移動を伸ばすと(x,y)への移動になる遷移
1は(xx,yy)が始点となる遷移
この遷移が発生するのはS[y][x]もS[yy][xx]も'.'である場合のみである。
　
dp2(x,y,d)もほぼ同様。
(x,y)からd移動した先を(xx,yy)とする。
すると、dp2(x,y,d) = dp2(xx,yy,d) + dp(xx,yy,(d+3)%4)となる。
dp2(xx,yy,d)は(xx,yy)から1つ移動を伸ばすと(x,y)への移動になる遷移
dp(xx,yy,(d+3)%4)は(xx,yy)で曲がってきた場合の遷移。(d+3)%4は実装上の書き方であるが、時計逆周りの方向に向けている。
　
※hamayanhamayanのdxdy運用
0↑1→2↓3←としているので、+1すると時計回り、-1すると反時計回りの移動方向になる。
実装では-1する代わりに+3している。

int H, W;
string S[2010];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
//---------------------------------------------------------------------------------------------------
int vis[2010][2010], vis2[2010][2010];
ll memo[2010][2010], memo2[2010][2010];
ll dp(int x, int y, int d) {
    if (vis[y][x]) return memo[y][x];
 
    int xx = x + dx[d], yy = y + dy[d];
    if (0 <= xx and xx < W and 0 <= yy and yy < H) {
        if (S[y][x] == '.' and S[yy][xx] == '.') {
            vis[y][x] = 1;
            return memo[y][x] = dp(xx, yy, d) + 1;
        }
    }
 
    vis[y][x] = 1;
    return memo[y][x] = 0;
}
ll dp2(int x, int y, int d) {
    if (vis2[y][x]) return memo2[y][x];
 
    int xx = x + dx[d], yy = y + dy[d];
    if (0 <= xx and xx < W and 0 <= yy and yy < H) {
        if (S[y][x] == '.' and S[yy][xx] == '.') {
            vis2[y][x] = 1;
            return memo2[y][x] = dp2(xx, yy, d) + dp(xx, yy, (d + 3) % 4);
        }
    }
 
    vis2[y][x] = 1;
    return memo2[y][x] = 0;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> S[y];
 
    ll ans = 0;
    rep(d, 0, 4) {
        rep(y, 0, H) rep(x, 0, W) vis[y][x] = vis2[y][x] = 0;
        rep(y, 0, H) rep(x, 0, W) ans += dp2(x, y, d);
    }
 
    cout << ans << endl;
}