目录
P1219 八皇后 Checker Challenge
题目描述
一个如下的 6 * 6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。
上面的布局可以用序列 2 4 6 1 3 5来描述，第 i 个数字表示在第 i 行的相应位置有一个棋子，如下：
行号 1 2 3 4 5 6
列号 2 4 6 1 3 5
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 3 个解。最后一行是解的总个数。
【数据范围】
对于 100% 的数据，6 ≤ n ≤ 13。
输入格式
一行一个正整数 n，表示棋盘是 n×n 大小的。
输出格式
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。
输入样例
6
输出样例
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
题解
八皇后问题是经典的搜索问题，题中要求求出所有解得个数，显然或想到使用回溯的方法，利用递归遍历整个棋盘，将符合条件的位置标记起来，然后递归下一层，以此得到相应的解。下面是回溯的模板。
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
代码如下：
#include<iostream>
using namespace std;
#define maxn 100
int a[maxn], b[maxn], c[maxn], d[maxn];
//四个数组分别用来表示行，列，主对角线及其平行线（i + j相同），次对角线及其平行线（i - j相同）
int ans = 0, n;
void show() {
for (int i = 1; i <= n; i++) {
cout << a[i] << " ";
}
cout << endl;
}
void search(int i) {
if (i > n) {
if (ans < 3)
show();
ans++;
return;
}
for (int j = 1; j <= n; j++) {
if (!b[j] && !c[i + j] && !d[i - j + n]) {
a[i] = j;
b[j] = 1;
c[i + j] = 1;
d[i - j + n] = 1;
search(i + 1);
b[j] = 0;//回溯
c[i + j] = 0;
d[i - j + n] = 0;
}
}
}
int main() {
cin >> n;
search(1);
cout << ans;
return 0;
}
P1123 取数游戏
题目描述
一个 N×M 的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻88个格子中的一个即认为这两个数字相邻），求取出数字和最大是多少。
对于100%100%的数据，N, M ≤ 6, T≤20。
输入格式
第1行有一个正整数T，表示了有T组数据。
对于每一组数据，第一行有两个正整数N和M，表示了数字矩阵为N行M列。
接下来N行，每行M个非负整数，描述了这个数字矩阵。
输出格式
T行，每行一个非负整数，输出所求得的答案。
输入样例
3
4 4
67 75 63 10
29 29 92 14
21 68 71 56
8 67 91 25
2 3
87 70 85
10 3 17
3 3
1 1 1
1 99 1
1 1 1
输出样例
271
172
99
题解
这是一道 dfs 的简单题目，要取得不相邻的几个数的最大值，每遍历一次数组可得到一次最大值，采用回溯标记的方法，对每次遍历取得的最大值进行比较，得到最终答案
代码如下：
#include<iostream>
using namespace std;
int N, M;
#define maxn 100
int a[maxn][maxn];
int vis[maxn][maxn];
int ans = 0;
void dfs(int x, int y, int value) {
if (x > N) {//若搜索完整个矩阵，则更换最大值
ans = max(ans, value);
return;
}
int nextx = x, nexty = y + 1;
if (nexty > M) {//若列超出范围，则更换下一行
nextx = x + 1, nexty = 1;
}
if (!vis[x - 1][y] && !vis[x][y - 1] && !vis[x - 1][y - 1] && !vis[x - 1][y + 1]) {//判断条件
vis[x][y] = 1;
dfs(nextx, nexty, value + a[x][y]);
vis[x][y] = 0;//回溯
}
dfs(nextx, nexty, value);//若不取这个数
}
int main() {
int T;
cin >> T;
while (T--) {
ans = 0;
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> a[i][j];
}
}
dfs(1, 0, 0);
cout << ans << endl;
}
}
P1135 奇怪的电梯
题解
题中要求求得最少的按键次数，可以看出这是一道简单的 bfs 搜索题目，对每一层的上楼或者下楼进行层次遍历，根据最终结果判断是否可以到达相应楼层
代码如下：
#include<iostream>
#include<queue>
using namespace std;
int n, a, b;
#define maxn 1000
bool vis[maxn];
int button[maxn];
int ans = 0;
struct node {
int floor;
int step;
};
node bfs(node p) {
queue<node> q;
q.push(p);
vis[p.floor] = 1;
node x;
while (!q.empty()) {
x = q.front();
q.pop();
if (x.floor == b) {
return x;
} else {
node next;
next.step = x.step + 1;
if (x.floor + button[x.floor] <= n && !vis[x.floor + button[x.floor]]) {
next.floor = x.floor + button[x.floor];
q.push(next);
vis[next.floor] = 1;
}
if (x.floor - button[x.floor] >= 1 && !vis[x.floor - button[x.floor]]) {
next.floor = x.floor - button[x.floor];
q.push(next);
vis[next.floor] = 1;
}
}
}
return x;
}
int main() {
cin >> n >> a >> b;
for (int i = 1; i <= n; i++) {
cin >> button[i];
}
node p;
p.floor = a, p.step = 0;
node t = bfs(p);
if (t.floor == b) cout << t.step << endl;
else cout << -1 << endl;
}
P3958 奶酪
题解
使用 dfs 搜索每一个洞，符合条件就退出，相比于 bfs 广度搜索，在这种问题里面，dfs要跑的数据量会更少，速度也更快
AC代码如下：
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 1010;
struct cir {
double x, y, z;
bool operator<(const cir &cpr) const {
return z < cpr.z;
}
} p[maxn];
bool fnd = 0;
int n;
double h, r;
bool vis[maxn];
double dist(double x1, double y1, double z1, double x2, double y2, double z2) {
return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + (z2 - z1) * (z2 - z1));
}
void dfs(cir now, int num) {
if (now.z + r >= h) {
fnd = 1;
return;
}
vis[num] = 1;
for (int i = 1; i <= n; i++) {
if (fnd)
return;
if (!vis[i] && dist(now.x, now.y, now.z, p[i].x, p[i].y, p[i].z) <= r * 2)
dfs(p[i], i);
}
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
memset(vis, 0, sizeof(vis));
memset(p, 0, sizeof(p));
fnd = 0;
scanf("%d%lf%lf", &n, &h, &r);
for (int i = 1; i <= n; i++)
scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].z);
std::sort(p + 1, p + n + 1);
for (int i = 1; i <= n; i++)//lower
if (p[i].z - r <= 0)
dfs(p[i], i);
if (fnd)
puts("Yes");
else
puts("No");
}
return 0;
}
P1443 马的遍历
题解
典型的 bfs 入门题目，十分丢脸的是，最近用惯了MATLAB，bfs孩子结点的时候的 for 循环默认使用缩进代替括号，调试了好久……
AC代码如下：
#include <cstdio>
#include <string.h>
#include <cmath>
#include <queue>
using namespace std;
struct node {
int x, y;
int step;
};
const int xx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
const int yy[8] = {2, -2, 2, -2, 1, -1, 1, -1};
#define maxn 405
int a[maxn][maxn];
bool vis[maxn][maxn];
int n, m;
void bfs(node p) {
a[p.x][p.y] = p.step;
queue<node> q;
q.push(p);
vis[p.x][p.y] = 1;
while (!q.empty()) {
node x = q.front();
node next;
q.pop();
for (int i = 0; i < 8; i++) {
next.x = x.x + xx[i], next.y = x.y + yy[i], next.step = x.step + 1;
if (next.x >= 1 && next.x <= n && next.y >= 1 && next.y <= m && !vis[next.x][next.y]) {
q.push(next);
vis[next.x][next.y] = 1;
a[next.x][next.y] = next.step;
}
}
}
}
int main() {
memset(vis, false, sizeof(vis));
memset(a, -1, sizeof(a));
int x, y;
scanf("%d%d%d%d", &n, &m, &x, &y);
node p;
p.x = x, p.y = y, p.step = 0;
bfs(p);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
printf("%-5d", a[i][j]);
printf("\n");
}
return 0;
}
acwing 845. 八数码
题解
八数码应该是今天碰到的最难的题了，不同于上边问题的直观搜索，八数码需要将目标对象进行转换，将图像转化为字符串，转变为判断字符串是否相等即可
AC代码如下：
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
int bfs(string start)
{
//定义目标状态
string end = "12345678x";
//定义队列和dist数组
queue<string> q;
unordered_map<string, int> d;
//初始化队列和dist数组
q.push(start);
d[start] = 0;
//转移方式
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
while(q.size())
{
auto t = q.front();
q.pop();
//记录当前状态的距离，如果是最终状态则返回距离
int distance = d[t];
if(t == end) return distance;
//查询x在字符串中的下标，然后转换为在矩阵中的坐标
int k = t.find('x');
int x = k / 3, y = k % 3;
for(int i = 0; i < 4; i++)
{
//求转移后x的坐标
int a = x + dx[i], b = y + dy[i];
//当前坐标没有越界
if(a >= 0 && a < 3 && b >= 0 && b < 3)
{
//转移x
swap(t[k], t[a * 3 + b]);
//如果当前状态是第一次遍历，记录距离，入队
if(!d.count(t))
{
d[t] = distance + 1;
q.push(t);
}
//还原状态，为下一种转换情况做准备
swap(t[k], t[a * 3 + b]);
}
}
}
//无法转换到目标状态，返回-1
return -1;
}
int main()
{
string c, start;
//输入起始状态
for(int i = 0; i < 9; i++)
{
cin >> c;
start += c;
}
cout << bfs(start) << endl;
return 0;
}