這篇文章主要講解了“如何用C++實(shí)現(xiàn)搭積木小游戲”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“如何用C++實(shí)現(xiàn)搭積木小游戲”吧！

創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),寬城企業(yè)網(wǎng)站建設(shè),寬城品牌網(wǎng)站建設(shè),網(wǎng)站定制,寬城網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營銷,網(wǎng)絡(luò)優(yōu)化,寬城網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競爭力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

小明對(duì)搭積木非常感興趣。他的積木都是同樣大小的正立方體。
在搭積木時(shí)，小明選取 m 塊積木作為地基，將他們?cè)谧雷由弦蛔峙砰_，中間不留空隙，并稱其為第0層。
隨后，小明可以在上面擺放第1層，第2層，……，最多擺放至第n層。擺放積木必須遵循三條規(guī)則

規(guī)則1：每塊積木必須緊挨著放置在某一塊積木的正上方，與其下一層的積木對(duì)齊；

規(guī)則2：同一層中的積木必須連續(xù)擺放，中間不能留有空隙；

規(guī)則3：小明不喜歡的位置不能放置積木。

其中，小明不喜歡的位置都被標(biāo)在了圖紙上。圖紙共有n行，從下至上的每一行分別對(duì)應(yīng)積木的第1層至第n層。每一行都有m個(gè)字符，字符可能是‘.'或‘X'，其中‘X'表示這個(gè)位置是小明不喜歡的。
現(xiàn)在，小明想要知道，共有多少種放置積木的方案。他找到了參加藍(lán)橋杯的你來幫他計(jì)算這個(gè)答案。
由于這個(gè)答案可能很大，你只需要回答這個(gè)答案對(duì)1000000007(十億零七)取模后的結(jié)果。
注意：地基上什么都不放，也算作是方案之一種。

輸入格式：
數(shù)據(jù)的第一行有兩個(gè)正整數(shù)n和m，表示圖紙的大小。
隨后n行，每行有m個(gè)字符，用來描述圖紙 。每個(gè)字符只可能是‘.'或‘X'。

輸出格式：
一個(gè)整數(shù)，表示答案對(duì)1000000007取模后的結(jié)果。

輸入樣例1：

2 3

..X

.X.

輸出樣例1：

4

輸入樣例2：

3 3

..X

.X.

...

輸出樣例2：

16

解題思路：

首先先推導(dǎo)出遞推式，觀察題目：

用代碼表示即為：

for(int c=1;c
意思是
在第i層的a到b長度放置積木的可能數(shù)=在i-1層的所有包含a到b的長度的積木的可能數(shù)的和。
除了單純的判斷遞推式以外，還需要考慮一種特殊情況，就是積木放置的長度中存在X，即小明不想放的位置，那么就不需要進(jìn)行遞推，直接返回0。
判斷[a,b]是否存在X，可以用前綴和來判斷，節(jié)省時(shí)間。
前綴和初始化為：
s[i][j] = s[i][j-1] + (temp=='X');
推導(dǎo)出遞推式以后可以很容易的寫出代碼：
#include

using namespace std;

const int N = 30;
int n, m;
int dp[30][30][30];
int s[30][30];
int cnt=1;

int main() {
	cin >> n >> m;
	getchar();
	for (int i = n; i >0; i--) {//初始化前綴和
		for (int j = 1; j <= m; j++) {
			char temp = getchar();
			s[i][j] = s[i][j-1] + (temp=='X');
		}
		getchar();
	}
	dp[0][1][m]=1;//第0層，長度從1到m的積木有一種可能
	for (int i = 1; i <=n; i++) {//第i層
		for (int a = 1; a <= m; a++) {
			for (int b = a; b <= m; b++) {
				if (s[i][b] - s[i][a - 1] != 0) {//a到b區(qū)間存在X
					dp[i][a][b] = 0;
					continue;
				}
				for (int c = 1; c <= a; c++) {
					for (int d = b; d <= m; d++) {
						dp[i][a][b] += dp[i - 1][c][d];
					}
				}
				cnt += dp[i][a][b];//記錄數(shù)量
			}
		}
	}
	cout << cnt;
	return 0;
}
優(yōu)化
但是仔細(xì)一想，五個(gè)for循環(huán)無法通過最后50%的測(cè)試點(diǎn)，所以需要進(jìn)行優(yōu)化，觀察最內(nèi)層的兩個(gè)c，d的for循環(huán)可知，有如下圖像：
實(shí)際上最內(nèi)層的兩個(gè)循環(huán)就是在求第i-1層的紅色區(qū)域面積。
那我們?cè)倮枚S的前綴和進(jìn)行存儲(chǔ)，那就可以優(yōu)化掉兩個(gè)循環(huán)，從而使時(shí)間復(fù)雜度降低，通過最后的測(cè)試點(diǎn)。
#include

using namespace std;

const int N = 30;
const int mod = 1e9 + 7;
int n, m;
int dp[30][30][30];
int s[30][30];//用來判斷是否存在X
int sum[30][30];//指的是左下角所有dp[i][][]的和
int cnt=1;

void get_fixsum(int i) {
	//更新第i層的前綴和數(shù)組
	for (int a = 1; a <= m; a++) {
		for (int b = 1; b <= m; b++) {
			sum[a][b] =(sum[a][b-1]+sum[a-1][b]-sum[a-1][b-1]+ dp[i][a][b])%mod;
		}
	}
}

int main() {
	cin >> n >> m;
	getchar();
	for (int i = n; i >0; i--) {
		for (int j = 1; j <= m; j++) {
			char temp = getchar();
			s[i][j] = s[i][j-1] + (temp=='X');
		}
		getchar();
	}
	dp[0][1][m]=1;//第0層，長度從1到m的積木有一種可能
	get_fixsum(0);
	for (int i = 1; i <=n; i++) {//層數(shù)
		for (int a = 1; a <= m; a++) {
			for (int b = a; b <= m; b++) {
				if (s[i][b] - s[i][a - 1] != 0) {//a到b區(qū)間存在X
					dp[i][a][b] = 0;
					continue;
				}
				dp[i][a][b] = (sum[a][m] - sum[0][m] - sum[a][b-1] + sum[0][b-1])%mod;
				cnt =(cnt+ dp[i][a][b])%mod;
			}
		}
		get_fixsum(i);
	}
	cout << (cnt+mod)%mod;//防止出現(xiàn)負(fù)數(shù)
	return 0;
}
感謝各位的閱讀，以上就是“如何用C++實(shí)現(xiàn)搭積木小游戲”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)如何用C++實(shí)現(xiàn)搭積木小游戲這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！
            
            
                        

            文章名稱：如何用C++實(shí)現(xiàn)搭積木小游戲            

            文章來源：http://weahome.cn/article/jjdpeg.html