next_permutation 二維數(shù)組 康拓

這個博客講了怎么算排列組合的第N個數(shù) 也就是康拓和康拓逆展開
https://blog.csdn.net/c18219227162/article/details/50301513

如【圖1.jpg】, 有12張連在一起的12生肖的郵票。
現(xiàn)在你要從中剪下5張來，要求必須是連著的。
（僅僅連接一個角不算相連）
比如，【圖2.jpg】，【圖3.jpg】中，粉紅色所示部分就是合格的剪取。

圖1.jpg

圖2.jpg

圖3.jpg

請你計算，一共有多少種不同的剪取方法。

請?zhí)顚懕硎痉桨笖?shù)目的整數(shù)。
注意：你提交的應(yīng)該是一個整數(shù)，不要填寫任何多余的內(nèi)容或說明性文字。

答案 116
搞懂了next_permutation的原理了 他是按照字典序 {0, 0, 1}是字典序的最小 而{1, 0, 0}這樣的是最大 這樣子就可以放心倒騰二維數(shù)組了 康拓函數(shù)也是這樣 所以這里設(shè)置的arr是{0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1};
next_permutation二維數(shù)組

#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;
}

一維數(shù)組

#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;
}