剪邮票

next_permutation 二维数组 康拓

这个博客讲了怎么算排列组合的第N个数 也就是康拓和康拓逆展开
https://blog.csdn.net/c18219227162/article/details/50301513

如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。

图1.jpg 图2.jpg 图3.jpg

请你计算，一共有多少种不同的剪取方法。

请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

答案 116
搞懂了next_permutation的原理了 他是按照字典序 {0, 0, 1}是字典序的最小 而{1, 0, 0}这样的是最大 这样子就可以放心倒腾二维数组了 康拓函数也是这样 所以这里设置的arr是{0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1};
next_permutation二维数组

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <sstream>
#include <algorithm>
int N = 3, M = 4, ans = 0;
int vis[3][4], arr[3][4];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
using namespace std;
struct node {
    int x, y;
    node (int a, int b) {
        x = a, y = b;
    }
};
void bfs(){
    fill(vis[0], vis[0] + 12, 0);
    queue<node> q;
    for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
    if (arr[i][j]) {
        vis[i][j] = 1;
        q.push(node(i, j));
        i = 1000;
         break;
    }
    int bl = 0;
    
    while (!q.empty()) {
        bl++;
        node no = q.front(); q.pop();
        int x = no.x, y = no.y;
        for (int i = 0; i < 4; i++) {
            int tx = x + dx[i];
            int ty = y + dy[i];
            if (tx < 0 || ty < 0 || tx >= N || ty >= M) continue;
            if (vis[tx][ty] || arr[tx][ty] == 0) continue;
            vis[tx][ty] = 1;
            q.push(node(tx, ty));
        }
    }
    if (bl == 5) ans++;
}
int main() {
    fill(arr[0] + 7, arr[0] + 12, 1);
    do {
        bfs();
    }while (next_permutation(arr[0], arr[0] + 12));
    cout << ans <<endl;
    return 0;
}

一维数组

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>

using namespace std;
int ar[12];
int vis[3][4];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int ans = 0;
queue <int> q;

int bfs(int pos) {
    int cnt = 0;
    fill(vis[0], vis[0] + 12, 0);
    q.push(pos);
    
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        int x = t / 4, y = t % 4;
        if (vis[x][y] || ar[t] == 0)    
            continue;
        vis[x][y] = 1;
        cnt++;
        for (int i = 0; i < 4; i++) {
            int tx = x + dx[i];
            int ty = y + dy[i];
            if (tx < 0 || ty < 0 || tx >= 3 || ty >= 4 || vis[tx][ty]) continue;
            int temp = tx * 4 + ty;
            q.push(temp);
        }
    }
    return cnt;
}
void ju(){
    for (int i = 0; i < 12; i++) {
        if (ar[i]) {
            if (bfs(i) == 5)
                ans++;
            return;
        }
    }
}
int main()
{
    fill(ar + 7, ar + 12, 1);
    do {
        ju();
    }while (next_permutation(ar, ar + 12));
    
    cout << ans;
    return 0;
}