No.86 TVザッピング(2)

No.86 TVザッピング(2) - yukicoder

• 一度だけ右に曲がる閉路を検出すればよいとこまではわかったが、それを普通に実装して TLE した。(計算量の落とし方がわからなかった。)
• 右にまがる地点をスタート地点にして、真っ直ぐか左にしかまがらないケースに限定して考えると、進めるときは真っ直ぐに進むしかないことに気づけたと思う。
• 考える条件を限定してやるととっかりがつかみやすいのかも。あと二歩くらい考察する癖をつけよう。
• 最初に cnt > 4*(N+M) なら return してやることで、計算量を大幅に減らせるのはすごいと思った。
• nd = (4+d+dd)%4 をうっかり nd = (d+dd)%4 と書いてしまってバグってしまっていた。

class TvZapping2 {
public:
    void solve(void) {
            int N,M;
            cin>>N>>M;

            int cnt = 0;
            vector<string> A(N);
            REP(i,N)
            {
                cin>>A[i];
                // 通過可能なボタンの総数を数えておく
                REP(j,M) if (A[i][j] == '.')
                    ++cnt;
            }

            //
            // 左に曲がる回数は以下のようなケースで最大 6 回まで
            //
            // ++++++++ +++
            // +      + + +
            // +      S++ +
            // +          +
            // ++++++++++++
            //
            // 閉路に含まれるマス数は 4*(N+M) 以下なのでそれ以上なら return
            // よって閉路探索時間と '.' 総数は K = 4*(N+M) 以下となる。
            if (cnt > 4*(N+M))
            {
                cout<<"NO"<<endl;
                return;
            }

            // sample 3 より最大一回は右に曲がってよいとしたとき、サイクルができればよさそう。
            // 以下の条件があるので計算量を落とせる
            //  * 右に曲がれるのはスタート地点のみ。スタート地点毎に計算をすれば左 or 真っ直ぐにしか進めないとみなせる
            //  * 左に曲がるとその先はもう進めなくなるので、それ以上すすめなくなるまで真っ直ぐ進む。
            // O(K^2) (K=4*(N+M))

            // 右回り
            const int dx[] = {-1,0,1,0};
            const int dy[] = {0,1,0,-1};

            // O(N+M)
            int sx, sy;
            function<bool(int,int,int,int)> search = [&](int x, int y, int d, int c) {
                for (int dd = 0; dd >= -1; --dd)
                {
                    int nd = (4+d+dd)%4;
                    int nx = x+dx[nd];
                    int ny = y+dy[nd];

                    if (nx < 0 || M <= nx || ny < 0 || N <= ny)
                        continue;

                    if (nx==sx && ny==sy)
                    {
                        if (cnt == c)
                            return true;
                        return false;
                    }
                    // 進めないなら左へ
                    if (A[ny][nx] != '.')
                        continue;

                    A[ny][nx] = '@'; // 通過フラグを立てておく
                    bool found = search(nx,ny,nd,c+1);
                    A[ny][nx] = '.';

                    if (found)
                        return true;
                    // まっすぐか左かしか移動しないので break する
                    break;
                }
                return false;
            };
            // O((N+M)^2)
            REP(d, 4)
            {
                REP(y,N)
                REP(x,M)
                {
                    if (A[y][x] != '.')
                        continue;
                    sx = x;
                    sy = y;
                    A[sy][sx] = '@';
                    if (search(sx,sy,d,1))
                    {
                        cout<<"YES"<<endl;
                        return;
                    }
                    A[sy][sx] = '.';
                }

            }
            cout<<"NO"<<endl;
    }
};