# BBQ

## 题目描述

You are a master of barbeque, and now you are trying to string dumplings with a bamboo stick.

The dumplings are placed in a $n \times m$ grid. Each grid contains exactly one dumpling. The color of each dumpling is red ("R"), green ("G") or white ("W").

You can choose three consecutive grids from left to right, or from top to bottom, and string the corresponding dumplings into a string from left to right or from top to bottom. So there will be exactly three dumplings on a string, let’s denote a string of dumpling by their colors in order.

Now, you want to make strings "RGW" as many as possible. Note that the dumplings can not be reused in multiple strings. So how many strings "RGW" can you make?

## 代码

#include <cstdio>
#include <cstring>
#include <algorithm>

int const N = 3005;
char mp[N][N];
int f[N][N][3];

int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%s", mp[i] + 1);
}
for (int k = 2; k <= n + m; ++k) {
for (int i = 1; i < k; ++i) {
int j = k - i;
if (i <= n && j <= m) {
f[i][j][0] = std::max(f[i - 1][j + 1][0], std::max(f[i - 1][j + 1][1], f[i - 1][j + 1][2]));
if (mp[i][j - 1] == 'R' && mp[i][j] == 'G' && mp[i][j + 1] == 'W') {
f[i][j][1] = std::max(f[i - 1][j + 1][0], f[i - 1][j + 1][1]) + 1;
}
if (mp[i - 1][j] == 'R' && mp[i][j] == 'G' && mp[i + 1][j] == 'W') {
f[i][j][2] = std::max(f[i - 1][j + 1][0], f[i - 1][j + 1][2]) + 1;
}
}
}
}
int ans = 0;
for (int i = 1; i < n; ++i) {
ans += std::max(f[i][1][0], std::max(f[i][1][1], f[i][1][2]));
}
for (int i = 1; i <= m; ++i) {
ans += std::max(f[n][i][0], std::max(f[n][i][1], f[n][i][2]));
}
printf("%d\n", ans);
return 0;
}

418 I'm a teapot