HDU 5319 Painter(2015多校联合)

发表于   |  

题目链接：

戳我

题目大意

一个画笔在画板作画。画笔有两种颜色，且只有两种画法，\ 和 /,\即沿着对角线的方向，同理。\只能是红色 R，/只能是蓝色 B。如果一个格子被B R个染一次，就变成绿色 G 。给一个最终状态的画布，求用最少几笔可以到达该最终状态。
每个格子只能被相同颜色染一次，画家可以选择任意起点作为画笔起点。
每一笔都是连续的。

样例解释

2
4
RR.B
.RG.
.BRR
B..R

解题思路

简单题。以每个G为起点，/和\各扫一次，最后在扫描有多少连续的\ R和/ B

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
//Author LJH
//www.cnblogs.com/tenlee
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#define clc(a, b) memset(a, b, sizeof(a))
using namespace std;

const int inf = 0x3f;
const int INF = 0x3f3f3f3f;
const int maxn = 100;
int movex[2][2] = {-1, -1, 1, 1};
int movey[2][2] = {-1, 1,  1, -1};

int n, m, g[maxn][maxn], ans;

bool judge(int x, int y)
{
    if(x < 1 || x > n || y < 1 || y > m) return  false;
    return true;
}
void findx(int x, int y)
{
    int a = x, b = y;
    g[x][y] -= 1;
    while(judge(a, b))
    {
        a += movex[0][0];
        b += movex[0][1];
        if(g[a][b] == 2 || g[a][b] == 0) break;
        g[a][b] -= 1;
    }
    a = x, b = y;
    while(judge(a, b))
    {
        a += movex[1][0];
        b += movex[1][1];
        if(g[a][b] == 2 || g[a][b] == 0) break;
        g[a][b] -= 1;
    }

}
void findy(int x, int y)
{
    g[x][y] -= 2;
    int a = x, b = y;
    while(judge(a, b))
    {
        a += movey[0][0];
        b += movey[0][1];
        if(g[a][b]  == 1 || g[a][b] == 0) break;
        g[a][b] -= 2;
    }
    a = x, b = y;
    while(judge(a, b))
    {
        a += movey[1][0];
        b += movey[1][1];
        if(g[a][b]  == 1 || g[a][b] == 0) break;
        g[a][b] -= 2;
    }
}

void Print()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            printf("%d", g[i][j]);
        }
        puts("");
    }
    puts("#####");
}
int main()
{
    //freopen("1.in", "r", stdin);
    int T;
    char col[maxn];
    char ch;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        clc(g, 0);
        ans = 0;
        for(int i = 1; i <= n; i++)
        {
            scanf(" %s", col);
            m = strlen(col);
            for(int j = 0; col[j]; j++)
            {   
                ch = col[j];
                if(ch == 'R') g[i][j+1] = 1;
                if(ch == 'B') g[i][j+1] = 2;
                if(ch == 'G') g[i][j+1] = 3;
                if(ch == '.') g[i][j+1] = 0;
            }
        }
        //Print();
        for(int i = 1; i <=n ;i++)
        {
            for(int j = 1; j <= m; j++)
            {
                if(g[i][j] == 3)
                {
                    ans += 2;
                    findx(i, j);
                    findy(i, j);
                }
            }
        }
        //Print();
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                if(g[i][j] == 1)
                {
                    ans++;
                    findx(i, j);
                    //Print();
                }
                if(g[i][j] == 2) 
                {
                    ans++;
                    findy(i, j);
                    //Print();
                }
            }
        }
        //Print();
        printf("%d\n", ans);
    }
    return 0;
}