剪邮票 - 简书

剪邮票

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

最后编辑于：2019.03.22 22:11:31