灌溉機(jī)器人

題目描述

農(nóng)田灌溉是一項(xiàng)十分費(fèi)體力的農(nóng)活，特別是大型的農(nóng)田。小明想為農(nóng)民伯伯們減輕農(nóng)作負(fù)擔(dān)，最近在研究一款高科技——灌溉機(jī)器人。它可以在遠(yuǎn)程電腦控制下，給農(nóng)田里的作物進(jìn)行灌溉。

現(xiàn)在有一片 N 行 M 列的農(nóng)田。農(nóng)田的土壤有兩種類型：類型 H 和類型 P，每一個格子上的土壤類型相同。其中類型 P 的土壤硬度較大，可以用來布置灌溉機(jī)器人，但是一個格子上只能布置一臺。類型 H 的土壤不能布置灌溉機(jī)器人。一臺灌溉機(jī)器人的灌溉區(qū)域如下圖所示：

黃色表示灌溉機(jī)器人布置的格子，紅色表示其灌溉區(qū)域，即四個方向上各外擴(kuò)展兩個格子。

小明想在農(nóng)田上盡可能多布置一些灌溉機(jī)器人，但是任意一臺機(jī)器人不能在任意一臺機(jī)器人的灌溉區(qū)域里，否則機(jī)器容易進(jìn)水出故障?，F(xiàn)在已知農(nóng)田每個格子的土壤類型，請你來幫小明計算一下，小明最多能布置多少臺灌溉機(jī)器人。

輸入描述

輸入第一行輸入兩個正整數(shù)N,M(N≤100,M≤10)，表示農(nóng)田的行和列。

接下來輸入 N 行，每行輸入連續(xù)的 M 個字符（P或者H），中間沒有空格。表示農(nóng)田每個格子上的土壤類型。

輸出描述

輸出一行，輸出一個整數(shù)，表示最多能擺放的灌溉機(jī)器人的數(shù)量。

用例輸入 1

3 4
PHPP
PHPP
PHHP

用例輸出 1

3

代碼

#include <bits/stdc++.h>
using namespace std;
#define max_Heap(x) priority_queue<x, vector<x>, less<x>>
#define min_Heap(x) priority_queue<x, vector<x>, greater<x>>
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
const double PI = acos(-1);int n, m;              // n行m列
char field[106][16];   // 記錄土壤是否能布置灌溉機(jī)器人
vector<int> s[106];    // 存儲第i行中所有的合法狀態(tài)
int dp[106][106][106]; // dp表示遍歷到第i行時，第i行狀態(tài)為序號j，第i-1行狀態(tài)為序號k時最大能擺放的機(jī)器人數(shù)量int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);unordered_map<int, int> mp;cin >> n >> m;for (int i = 1; i <= n; i++){for (int j = 0; j < m; j++){cin >> field[i][j]; // 讀入土壤類型}}// 預(yù)處理存儲第i行中所有的合法狀態(tài)for (int i = 1; i <= n; i++){for (int j = 0; j < (1 << m); j++){bool ok = 1; // 是否合法for (int k = 0; k < m; k++){if (((j >> k) & 1) && (field[i][k] == 'H')) // 如果在H類型土壤上放機(jī)器人，則不合法{ok = 0;break;}}if ((j & (j << 1)) || (j & (j << 2)) || (j & (j >> 1)) || (j & (j >> 2))) // 判斷左右方向擴(kuò)展的兩個格子是否合法{ok = 0;}if (ok)s[i].push_back(j);}}// 預(yù)處理每一行中各種放置狀態(tài)機(jī)器人的個數(shù)，并存儲在map中for (int i = 0; i < (1 << m); i++){int cnt = 0;for (int j = 0; j < m; j++){if ((i >> j) & 1)cnt++;}mp[i] = cnt;}// 初始化第一行的dpfor (int i = 0; i < s[1].size(); i++){dp[1][i][0] = mp[s[1][i]];}s[0].push_back(0);// 枚舉到第i行for (int i = 1; i <= n; i++){// 枚舉當(dāng)前行所有狀態(tài)for (int num3 = 0; num3 < s[i].size(); num3++){int s3 = s[i][num3];// 枚舉上一行所有狀態(tài)for (int num2 = 0; num2 < s[i - 1].size(); num2++){int s2 = s[i - 1][num2];// 枚舉上上一行所有狀態(tài)for (int num1 = 0; num1 < s[i - 2].size(); num1++){int s1 = s[i - 2][num1];// 如果三行之間的關(guān)系合法，則更新dpif (!(s1 & s2) && !(s1 & s3) && !(s2 & s3))dp[i][num3][num2] = max(dp[i][num3][num2], dp[i - 1][num2][num1] + mp[s3]);}}}}int ans = 0;// 遍歷找最大值for (int i = 0; i < s[n].size(); i++){for (int j = 0; j < s[n - 1].size(); j++){ans = max(ans, dp[n][i][j]);}}cout << ans;return 0;
}