2015年6月9日 星期二

2015/06/09 Codeforces 549D. Haar Features

/*
    從右下到左上greedy的 
    把原有數值改成目標的數值
*/
// http://codeforces.com/contest/549/problem/D
#include <iostream>
#include <cstdio>

using namespace std;

int N, M;
int now[200][200];
int goal[200][200];

char p[200];

void clear(int x, int y, int d)
{
    for(int xi = 0; xi <= x; xi++)
        for(int yi = 0; yi <= y; yi++)
            now[xi][yi] += d;
}

int main()
{
    scanf("%d %d", &N, &M);

    for(int Ni = 0; Ni < N; Ni++)
    {
        scanf("%s", p);

        for(int Mi = 0; Mi < M; Mi++)
            goal[Ni][Mi] = p[Mi], now[Ni][Mi] = -1;
    }


    int Ans = 0;

    for(int Ni = N-1; Ni >= 0; Ni--)
        for(int Mi = M-1; Mi >= 0; Mi--)
        {
            if( now[Ni][Mi] != goal[Ni][Mi] )
            {
                clear(Ni, Mi, goal[Ni][Mi]-now[Ni][Mi]);
                Ans++;
            }
        }

    printf("%d\n", Ans);
}

沒有留言:

張貼留言