在acwing上发现这个活动，写来玩玩，持续更新中~
kuangbin专题打卡活动

1. 棋盘问题

题意概括：
在一个 $n\times n$ 的棋盘上放 $k$ 个棋子的方案数，每行每列只能放一个，且只能放在值为 ‘#’ 的格子上。
$n\le 8,k\le n$

思路：
和八皇后问题的思路类似，递归每一行，在其中选择出一列放置，或者是该行不放，当放够了 $k$ 个棋子结果方案数加一并返回，递归到的行数超出了棋盘的大小则直接返回。

code：

#include <bits/stdc++.h>
using namespace std;char g[10][10];
bool vis[10];  // 第 j 列是否访问过
int n, k, res;void dfs(int i, int cnt) {if (k == cnt) { res ++; return; } // 放满了k个if (i >= n)     return;  // 超出棋盘行数for (int j = 0; j < n; j++) { // 第 i 行放在第 j 列if (vis[j] || g[i][j] == '.') continue;vis[j] = true;dfs(i + 1, cnt + 1);vis[j] = false;}dfs(i + 1, cnt); // 第 i 行不放
}int main() {while (scanf("%d%d", &n, &k)) {if (n == -1) break;for (int i = 0; i < n; i++) scanf("%s", &g[i]);res = 0;memset(vis, false, sizeof(vis));dfs(0, 0);printf("%d\\n", res);}return 0;
}

无关紧要的状态优化：
如果擅长位运算，可以把代码写得简短一点，用一个 int 变量来代替 vis 数组记录每一列是否访问过。

code：

#include <bits/stdc++.h>
using namespace std;char g[10][10];
int n, k, res;// state：用该数二进制位表示第j列是否被占用
void dfs(int i, int cnt, int state) {if (k == cnt) { res ++; return; } // 放满了k个if (i >= n)     return;  // 超出棋盘行数for (int j = 0; j < n; j++) { // 第 i 行放在第 j 列if ((state >> j & 1) || g[i][j] == '.') continue;dfs(i + 1, cnt + 1, state | (1 << j));}dfs(i + 1, cnt); // 第 i 行不放
}int main() {while (scanf("%d%d", &n, &k)) {if (n == -1) break;for (int i = 0; i < n; i++) scanf("%s", &g[i]);res = 0;dfs(0, 0, 0);printf("%d\\n", res);}return 0;
}

2. 地牢大师

题意概括：
你在一个立方体中，每次可以向东南西北上下六个方向移动，从起点 $S$ 开始到终点 $E$，# 代表代表该位置有障碍走不通，求起点到终点的最小步数。

思路：
标准的BFS模板，不过是从从二维拓展到了三维，按照二维的思路写就行了。

#include <bits/stdc++.h>
using namespace std;// 地牢大师int L, R, C;
char g[104][104][104];  // 存图
bool vis[104][104][104];  // 记录是否访问过
int step[104][104][104]; // 存 (i,j,k) 到起点的距离
int dd[6][3] = {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}}; 
int sx, sy, sz; // 起始坐标
struct pos { // 坐标结构体int x, y, z;
};int bfs() {queue<pos> q;q.push({sx, sy, sz});vis[sx][sy][sz] = true;while (q.size()) {pos p = q.front(); q.pop();if (g[p.x][p.y][p.z] == 'E') return step[p.x][p.y][p.z];for (auto di: dd) {int nx = p.x + di[0], ny = p.y + di[1], nz = p.z + di[2];if (0>nx || 0>ny || 0>nz || nx>=L || ny>=R || nz>=C || vis[nx][ny][nz] || g[nx][ny][nz]=='#') continue;step[nx][ny][nz] = 1 + step[p.x][p.y][p.z];q.push({nx, ny, nz});vis[nx][ny][nz] = true;}}return -1;
}int main() {while (cin >> L >> R >> C, L && R && C) {memset(vis, false, sizeof(vis));memset(step, 0, sizeof(step));for (int i = 0; i < L; i++) {for (int j = 0; j < R; j++) {for (int k = 0; k < C; k++) {cin >> g[i][j][k];if (g[i][j][k] == 'S') sx = i, sy = j, sz = k;}}}int res = bfs();if (~res) cout << "Escaped in " << res << " minute(s)." << endl;else cout << "Trapped!" << endl;}return 0;
}

3. 抓住那头牛

手机号没绑定做不了那道题，等后面解决了再写

4.翻转

题意概括：
给你一个 $m\times n$ 且只包含 $0$ 和 $1$ 的矩阵，每次点击一个位置，当前位置和上下左右四个位置进行 $01$互换，要求找出最少翻转次数将矩阵转换为全 $0$，并记录每个位置点击了多少次，输出字典序最小点击次数。

思路：
二进制枚举第一行所有翻转的方案，然后翻转第一行，后面的行根据当前位置的上方格子是否为 $1$ 来判断是否翻转当前格子，如果上方为 $1$ 则需要翻转当前格子，当最后一行翻转完之后判断最后一行是否全 $0$，是则直接输出结果返回，如果第一行的所有方案枚举完最后一行都不能全 $0$，则不能将矩阵转换为全 $0$。

因为每次翻转完会改变原矩阵，所以需要一个备份矩阵来记录输入。

相似题目：acwing算法竞赛进阶指南打卡活动–费解的开关

code：

#include <bits/stdc++.h>
using namespace std;int m, n;
int g[16][16], bak[16][16], res[16][16]; // 翻转矩阵，备份矩阵，点击次数矩阵
int dd[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};void turn(int i, int j) { // 翻转g[i][j] ^= 1;for (auto di: dd) {int nx = i + di[0], ny = j + di[1];if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;g[nx][ny] ^= 1;}
}void solve() {for (int i = 0; i < 1 << n; i++) {memcpy(g, bak, sizeof(g));memset(res, 0, sizeof(res));for (int j = 0; j < n; j++)  // 先按第一行if (i >> j & 1) turn(0, j), res[0][j] ++;for (int x = 1; x < m; x++)  // 按后面的行for (int y = 0; y < n; y++) if (g[x-1][y] == 1) turn(x, y), res[x][y] ++;bool flag = true;for (int j = 0; j < n; j++)  // 判断最后一行是否全零if (g[m-1][j] == 1) { flag = false; break; }if (flag) {for (int x = 0; x < m; x++) {for (int y = 0; y < n; y++) {printf("%d ", res[x][y]);}puts("");}return;}}puts("IMPOSSIBLE");
}int main() {scanf("%d%d", &m, &n);for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)scanf("%d", &bak[i][j]);solve();return 0;
}