題目描述
如下圖, 有12張連在一起的12生肖的郵票。現(xiàn)在你要從中剪下5張來，要求必須是連著的。（僅僅連接一個(gè)角不算相連）

比如，下面兩張圖中，粉紅色所示部分就是合格的剪取。

請(qǐng)你計(jì)算，一共有多少種不同的剪取方法。
輸出
請(qǐng)?zhí)顚懕硎痉桨笖?shù)目的整數(shù)。

解題思路：
這題不能用dfs，原因是dfs無法處理下面這種情況：

dfs一路走到底，所以它沒辦法回頭，所以這題不能用dfs，那么我們可以用next_permutation函數(shù)枚舉所選的5個(gè)點(diǎn)，然后用dfs判斷是否連通。

代碼如下：

#include <iostream> #include <algorithm> using namespace std; const int N = 5; bool mp[N][N]; int cnt; int ans;int a[] = {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1};int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};void dfs(int x, int y) {if (x < 0 || x > 2 || y < 0 || y > 3)return;if (mp[x][y] != 1)return ;cnt++;if (cnt == 5) {ans++;return ;}mp[x][y] = 0;for (int i = 0; i < 4; i++) {int xx = x + dx[i], yy = y + dy[i];dfs(xx, yy);} }int main() {do {int px, py;for (int i = 0; i <= 2; i++)for (int j = 0; j <= 3; j++) {if (a[i * 4 + j] == 1) {//將一維數(shù)組映射到二維數(shù)組px = i;py = j;mp[i][j] = 1;} elsemp[i][j] = 0;}dfs(px, py);cnt = 0;} while (next_permutation(a, a + 12));cout << ans << endl;return 0; } #include <iostream> #include <algorithm> using namespace std; const int N = 5;int a[] = {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1};int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}; int cnt ; int px, py; int mp[N][N]; int ans;void dfs(int x, int y) {for (int i = 0; i < 4; i++) {int xx = x + dx[i];int yy = y + dy[i];if (xx < 0 || xx >= 3 || yy < 0 || yy >= 4 || !mp[xx][yy])continue;mp[xx][yy] = 0;cnt++;if (cnt == 5)ans++;dfs(xx, yy);} }int main() {do {for (int i = 0; i < 3; i++)for (int j = 0; j < 4; j++) {if (a[i * 4 + j] == 1) {mp[i][j] = 1;px = i;py = j;} elsemp[i][j] = 0;}cnt = 1;mp[px][py] = 0;dfs(px, py);} while (next_permutation(a, a + 12));cout << ans << endl;return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的[蓝桥杯2016初赛]剪邮票-dfs+next_permutation(好题)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。