网站开发php工程师,是普通网站地图好还是rss地图好一点,扬州市城乡建设网站,seo首页优化一、题目大意
我们要在N * M的田地里种植玉米#xff0c;有如下限制条件#xff1a;
1、对已经种植了玉米的位置#xff0c;它的四个相邻位置都无法继续种植玉米。
2、题目中有说一些块无论如何#xff0c;都无法种植玉米。
求所有种植玉米的方案数#xff08;不种植也…一、题目大意
我们要在N * M的田地里种植玉米有如下限制条件
1、对已经种植了玉米的位置它的四个相邻位置都无法继续种植玉米。
2、题目中有说一些块无论如何都无法种植玉米。
求所有种植玉米的方案数不种植也是一种方案
二、解题思路
不难看出本题目是铺砖问题我们可以先写一个基于递归解决的Domo。
可以定义数组color[i][j]代表该位置是否起初就无法种植
并定义数组used[i][j]代表该位置是否已经被旁边的块覆盖无法种植。
对于i j 位置判断它如果不能种植就直接计算下一个位置。
如果可以种植则分别尝试种植和不种植两种情况将计算出的方案数求和。
写出递归代码如下
int rec(int i, int j)
{if (i n){return 1;}if (j m){return rec(i 1, 0);}if (color[i][j] || used[i][j]){return rec(i, j 1);}int res 0;bool rt false, dn false;if (j 1 m){rt used[i][j 1];}if (i 1 n){dn used[i 1][j];}res rec(i, j 1);used[i][j] true;if (j 1 m){used[i][j 1] true;}if (i 1 n){used[i 1][j] true;}res rec(i, j 1);used[i][j] false;if (j 1 m){used[i][j 1] rt;}if (i 1 n){used[i 1][j] dn;}return res;
}
这个递归代码一定是超时的那么接下来考虑如何把它转成DP我们发现这个递归算法是从左上一直算到右下那么对于i j位置其实只需要记录 (rowi1colj)和(rowicolj)的一排元素是否可以种植玉米即可如下图所示。
所以不难看出对于同一个位置且这一排元素确定时算出的方案数也是确定的那么我们就可以从右下角开始一点点边计算边循环到左上角。
在这个计算的过程中和递归一样只需要考虑两点。
第一如果i j位置不能种植玉米则加上i j位置不种植时的下一块的值 crt[ S 去掉第 j 块 ]。
第二如果i j位置能够种植玉米则依次加上i j位置种植和不种植情况时下一块的值dp[S] 和 crt[S 加上第 j 块 和 第 j1 块]如果j1m则不用添加第j1块。
初始化时考虑到最后一块的情况如果它能够种植则是2如果不能则是1那么就可以初始化DP数组上一行的所有元素为1。
可以使用滑动数组求解循环计算每一块之后本次的当前行作为下次计算的上一行即可。
最终输出的答案为上一行的第一个位置。 三、代码
#include iostream
using namespace std;
const int MAX_M 12;
const int MAX_N 12;
int dp[2][1 MAX_M];
bool color[MAX_N][MAX_M];
int n, m;
void solve()
{int *crt dp[0], *next dp[1];fill(crt, crt (1 MAX_M), 1);for (int i n - 1; i 0; i--){for (int j m - 1; j 0; j--){for (int used 0; used (1 m); used){if (color[i][j] || (used j 1)){next[used] crt[used ~(1 j)];}else{int res crt[used];if (j 1 m){res crt[used | (1 (j 1)) | (1 j)];}else{res crt[used | (1 j)];}next[used] res % 100000000;}}swap(next, crt);}}printf(%d\n, crt[0]);
}
int main()
{scanf(%d%d, n, m);int num;for (int i 0; i n; i){for (int j 0; j m; j){scanf(%d, num);color[i][j] num 0;}}solve();return 0;
}
四、相关文献
《挑战程序设计竞赛第二版》P196-P198 铺砖问题
