WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM610 Div1 Easy & Div2 Medium "TheMatrix"

問題

TopCoder Statistics - Problem Statement

あなたは本物だと確信した夢を見たことがあるだろうか?あなたがその夢から醒めることができなかったら?どのようにして現実と夢を区別することができるだろうか?

その複雑なパズルに答えを見出すための方法の一つは、その世界でのチェス盤は正しい姿をしているかを調べることである。

マス同士が一辺を共有していた場合、それは隣り合ったマスとする。正しいチェス盤とは、まずマスの色は白か黒かのどちらかであり、白と黒が交互に敷き詰められ、隣り合うマスが同じ色にならないことである。

あなたは黒を0、白を1と表すString[] boardが与えられる。boardは0と1以外の文字は含まれていない。ここから正しいチェス盤となっている部分を長方形の形で切り取る時、その最大の面積を返せ。

制約

1 <= boardの縦幅・横幅 <= 100


考えたこと

なにこれwwwO(N^4)の方法しか思いつかないwwww
もういいやwwwさぶみっとwwwww
とおったwwwwwなにこれwwwww

O(N^3)

1.ボード発見
f:id:Ekaing:20140306014249j:plain

2.右方向にどれだけ正しい状態で伸びているか印を付ける
f:id:Ekaing:20140306014254j:plain

3.あるマスに着目し、下方向にどれだけ切り取ると面積が最大になるか調べる。
f:id:Ekaing:20140306014945j:plain

ソースコード

int L[105][105];

class TheMatrix {
public:

    int MaxArea(vector <string> B) {
        // 1.ボード発見
        int R = B.size();
        int C = B[0].size();

        // 2.右方向
        for (int y = 0; y < R; y++) {
            for (int x = C - 1; x >= 0; x--) {
                if (x == C - 1) {
                    L[y][x] = 1;
                }
                else {
                    if (B[y][x] == B[y][x + 1]) {
                        L[y][x] = 1;
                    } else {
                        L[y][x] = L[y][x + 1] + 1;
                    }
                }
            }
        }

        // 3.下方向
        int res = 0;
        for (int y = 0; y < R; y++) {
            for (int x = 0; x < C; x++) {
                int w = L[y][x];
                res = max(res, w);
                for (int y2 = y + 1; y2 < R && B[y2][x] != B[y2 - 1][x]; y2++) {
                    w = min(w, L[y2][x]);
                    int h = y2 - y + 1;
                    res = max(res, w * h);
                }
            }
        }

        return res;
    }
};