Looksery Cup 2015, problem: (D) Haar Features

有O(n^2) 沒好好推就是

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <cstring>
#include <map>
#include <cmath>
#include <utility>

using namespace std;

int mm[110][110];
int tmp[110][110];

void draw(int a, int b, int v){
    for(int lx = 0;lx < a;lx++)
        for(int ly = 0;ly < b;ly++)
            tmp[lx][ly] += v;
    return;
}

void prt(int a, int b){
    for(int lx = 0;lx < a;lx++){
        for(int ly  = 0;ly < b;ly++)
            printf("%c", tmp[lx][ly] ? 'W':'B');
        puts("");
    }
    return;
}

int main(){
    int n, m; scanf("%d %d", &n, &m);
    for(int lx = 0;lx < n;lx++){
        char buf[200]; scanf("%s", buf);
        for(int ly = 0;ly < m;ly++)
            mm[lx][ly] = (buf[ly] == 'W');
    }
    int cnt = 1;
    for(int lx = 0;lx < n;lx++)
        for(int ly = 0;ly < m;ly++)
            tmp[lx][ly] = mm[n-1][m-1];
    //prt(n, m);
    for(int cc = n+m-3;cc>=0;cc--){
        for(int x = 0;x <= cc;x++){
            int y = cc-x;
            if(x >= n or y >= m) continue;
            if(tmp[x][y] != mm[x][y]){
                draw(x+1, y+1, mm[x][y]-tmp[x][y]), cnt++;
                //printf("draw at %d %d\n", x, y);
                //prt(n, m);
            }
        }
    }
    printf("%d\n", cnt);
    return 0;
}