「一本通 5.4 练习 2」炮兵阵地
题目描述
司令部的将军们打算在N\times MN×M的网格地图上部署他们的炮兵部队。一个N\times MN×M的地图由 N 行 M 列组成，地图的每一格可能是山地（用 H 表示），也可能是平原（用 P 表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
输入格式
第一行包含两个由空格分割开的正整数，分别表示 N 和 M； 接下来的 N 行，每一行含有连续的 M 个字符（P 或者 H），中间没有空格。按顺序表示地图中每一行的数据。
输出格式
仅一行，包含一个整数 K，表示最多能摆放的炮兵部队的数量。
样例
输入数据 1
5 4
PHPP
PPHH
PPPP
PHPP
PHHP
[Copy](javascript:
输出数据 1
6
[Copy](javascript:
数据范围与提示
N\le 100, M\le 10N≤100,M≤10。
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#define up(l, r, i) for (int i = l, END##i = r; i <= END##i; ++i)
#define _up(l, r, i) for (int i = l, END##i = r; i < END##i; ++i)
#define dn(r, l, i) for (int i = r, END##i = l; i >= END##i; --i)
#define _dn(r, l, i) for (int i = r, END##i = l; i > END##i; --i)
// #define int long long
#define ll long long
#define endl '\n'
#define fast \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
const int N = 114514 / 1000;
const int INF = 0x3f3f3f3f;
const int _INF = -0x3f3f3f3f;
const int MOD = 998244353;
int n, m, ans, maxn;
char g[N][N];
int vis[N][N];
bool isOK(int x, int y)
{
if (g[x][y] != 'P')
return false;
up(1, 2, i)
{
if (x - i >= 0 && vis[x - i][y])
return false;
if (x + i < n && vis[x + i][y])
return false;
if (y - i >= 0 && vis[x][y - i])
return false;
if (y + i < m && vis[x][y + i])
return false;
}
return true;
}
void dfs(int x, int y)
{
if (x == n)
{
if (ans > maxn)
maxn = ans;
return;
}
int nx = x, ny = y + 1;
if (ny == m)
{
nx = x + 1;
ny = 0;
}
if (isOK(x, y))
{
vis[x][y] = 1;
ans++;
dfs(nx, ny);
ans--;
vis[x][y] = 0;
}
dfs(nx, ny);
}
int main()
{
fast;
cin >> n >> m;
up(0, n, i)
{
cin >> g[i];
}
dfs(0, 0);
cout << maxn << endl;
return 0;
}