hdoj 5319 Painter(模拟题)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5319

思路分析：假设颜色R表示为1，颜色B表示为2，颜色G表示为3，因为数据量较小，采用暴力解法即可，即每次扫描对角线，看每条对角线需要画多少笔，统计所有对角线的笔数和即可；

代码如下：

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

const int MAX_N =  + ;

int map[MAX_N][MAX_N];

int Solve(int n, int m)

{

    // m 表示行, n表示列数

    int count = ;

    bool flag = false;

    for (int k = m - ; k >=  - n; -- k)

    {

        flag = false;

        for (int j = ; j < n; ++ j)

        {

            int i = j + k;

            if ( <= i && i < m &&  <= j && j < n)

            {

                if (map[i][j] & )

                {

                    map[i][j] = map[i][j] - ;

                    if (!flag)

                    {

                        flag = true;

                        count++;

                    }

                }  else if ((map[i][j] & ) ==  && flag)

                    flag = false;

            }

        }

    }

    flag = false;

    int t = m + n;

    for (int k = ; k < t; ++ k)

    {

        flag = false;

        for (int j = ; j < n; ++ j)

        {

            int i = -j + k;

            if ( <= i && i < m &&  <= j && j < n)

            {

                if (map[i][j] & )

                {

                    map[i][j] = map[i][j] - ;

                    if (!flag)

                    {

                        flag = true;

                        count++;

                    }

                } else if ((map[i][j] & ) ==  && flag)

                    flag = false;

            }

        }

    }

    return count;

}

int main()

{

    int case_times;

    char str[MAX_N];

    int n, m;

    scanf("%d", &case_times);

    while (case_times--)

    {

        scanf("%d", &n);

        memset(map, , sizeof(map));

        for (int i = ; i < n; ++ i)

        {

            scanf("%s", str);

            int len = m = strlen(str);

            for (int j = ; j < len; ++ j)

            {

                if (str[j] == '.')

                    map[i][j] = ;

                if (str[j] == 'R')

                    map[i][j] = ;

                if (str[j] == 'B')

                    map[i][j] = ;

                if (str[j] == 'G')

                    map[i][j] = ;

            }

        }

        int ans = Solve(m, n);

        printf("%d\n", ans);

    }

    return ;

}