状态压缩+DFS
时间复杂度O($2^n$),小于排列的O($n!$)
12张邮票,要剪下5张,则可以用12位二进制数来枚举所有邮票剪切情况
1表示剪下,0表示没剪下,然后把这串二进制数转成二维矩阵,然后DFS搜连通块,如果连通块数量为1,则说明是一个合法状态,计数加一
例如0100,0110,0011
转成二维矩阵:
0100
0110
0011
显然所有1在一个连通块内,即邮票都连在一起,这是一组合法状态
对于一个一维数组a[i]
,其转成二维数组的下标是b[i / c][i % c]
, c表示列数, 下标从0开始(c++二维数组是行优先存储方式)
#include <bits/stdc++.h>
using namespace std;
int mp[3][4];
bool visited[3][4];
int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void dfs(int x, int y)
{
if (x < 0 || x > 2 || y < 0 || y > 3) return;
if (visited[x][y]) return;
visited[x][y] = true;
for (int i = 0; i < 4; i++)
{
int nx = x + d[i][0], ny = y + d[i][1];
if (nx < 0 || nx > 2 || ny < 0 || ny > 3) continue;
if (visited[nx][ny]) continue;
if (mp[nx][ny] == 0) continue;
dfs(nx, ny);
}
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int res = 0;
int count = 0;
//用12位二进制位枚举每个状态
for (int i = 0; i <= (1 << 12) - 1; i++)
{
int tmp = i, cnt = 0;
//计算当前状态中有几个1
//tmp &= tmp - 1可以消去tmp中最低位的1
while (tmp)
{
tmp &= tmp - 1;
cnt++;
}
if (cnt != 5) continue; //只留下5个1的状态
memset(mp, 0, sizeof mp);
memset(visited, 0, sizeof visited);
//把状态转换成二维矩阵
for (int j = 11; j >= 0; j--)
{
//a[i]映射到二维数组mp[x][y]: a[i] = mp[i / 4][i % 4],下标从0开始
//状态压缩技巧
if ((i >> j) & 1) mp[(11 - j) / 4][(11 - j) % 4] = 1;
}
int conn = 0; //记录连通块数量
//dfs搜索所有连通块
for (int r = 0; r < 3; r++)
for (int c = 0; c < 4; c++)
{
if (!visited[r][c] && mp[r][c] == 1)
{
dfs(r, c);
conn++;
}
}
if (conn == 1) res++; //如果只有一个连通块,则是一个合法状态
}
cout << res; //答案为116
return 0;
}