简单搜索
[poj1321](##POJ1321 – 棋盘问题 )
POJ1321 – 棋盘问题
题解
变版的八皇后问题，只不过棋盘不再规则只能在某些格子放棋子而已，思路不变。先假设前面k行已经摆好且没有相互矛盾，那在第k+1行就有摆和不摆两种选择，如果摆，那又有摆在哪一列的选择，用一个col数组记录前面哪些列已经用过了，如果col[x]的状态表示没有用过，那[k+1][x]就是一个可行的位置，把col[x]标记一下，然后继续向下一行探索。
#include<iostream>
#include<cstring>
using namespace std;
bool col[10];//存哪些列用过来了,false表示没用过
char grid[10][10];//存图
int n, k, ans;
void dfs(int line, int num) {//line表示现在在第几行，num表示前面填好了几个
if (line==n||num == k) {//行号最多n-1,到n肯定不行了
if (num == k)//如果已经填好k个，总方案数加1
ans++;
return;
}
for (int i = 0; i < n; i++) {
//在该行填，将改行的每一列遍历一遍，看看哪些列可以填
if (!col[i] && grid[line][i] == '#') {
col[i] = true;
dfs(line + 1, num + 1);
col[i] = false;//j
}
}
//不在改行填，所以num没有加1
dfs(line + 1, num);
}
int main()
{
while (cin >> n >> k) {
if (n == k && n == -1)
break;
memset(col, false, sizeof(col));//初始化
ans = 0;
for (int i = 0; i < n; i++) {
cin >> grid[i];
}
dfs(0, 0);//从第0行开始，已经填好0个
cout << ans << endl;
}
return 0;
}
[POJ3278](3278 – Catch That Cow (poj.org))
题解
该题注意剪枝，不让会RE（虽然我用的map），剪枝不可将x+1>K和x*2>k的情况剪掉，例如100->199
另外由于时间卡得比较紧，数量比较大所以不能用map，用map会TE
poj3279
题意大概说的是给定一个m*n的01矩阵，每次去翻一个位置周围四个方向的位置都会翻转，问能不能翻到全是0，能的话输出字典序最小的翻法
题解
这是遇到的第一个枚举题，二进制枚举，首先确定的是每个位置只有翻和不翻两种情况，翻两次等于没翻，翻奇数次等于一次。如果去考察每一个位置的翻的情况就会有2^mn^次结果，显然时间超限，观察（看博客）易得出规律——==假设第一行的状态确定（就是第一行哪些位置翻不翻确定，确定之后会得到第一行确定的状态，哪些位置是0哪些是1），从第二行开始扫描，如果发现该位置上头上的位置为1那该位置一定要翻，因为头上的位置上左右都确定了==，以此扫描完整个数组，最后再对最后一行做一个检查，如果有1则不行，因为现在只能由下一行来翻转该位置，但没有下一行。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> using namespace std; const int maxn = 20; int n, m; int maze[maxn][maxn]; int grid[maxn][maxn]; int ans[maxn][maxn]; int dir[5][2] = { {0,0},{1,0},{0,1},{-1,0},{0,-1} }; bool legal(int x, int y) { return (x >= 0 && x < n&& y >= 0 && y < m); } void flip(int x, int y) { ans[x][y] = 1; int nx, ny; for (int i = 0; i < 5; i++) { nx = x + dir[i][0]; ny = y + dir[i][1]; if (legal(nx, ny)) { grid[nx][ny] ^= 1; } } } void solve() { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { printf("%d%c", ans[i][j], " \n"[j == (m - 1)]); } } } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%d", &maze[i][j]); } } int end = 1 << m; int bsk; bool ok = true; for (int i = 0; i < end; i++) { ok = true; bsk = i; memcpy(grid, maze, sizeof(maze)); memset(ans, 0, sizeof(ans)); for (int k = 0; k < m; k++) { if (bsk & 1) flip(0, k); bsk >>= 1; } for (int j = 1; j < n; j++) { for (int k = 0; k < m; k++) { if (grid[j - 1][k]) flip(j, k); } } for (int k = 0, j = n - 1; k < m; k++) { if (grid[j][k]) { ok = false; continue; } } if (ok) { solve(); break; } } if (!ok) printf("IMPOSSIBLE\n"); return 0; }
POJ1426 – Find The Multiple
题意大概是给一个数字n,找出一个n的十进制倍数m，m只能由01组成
题解
虽然这道题说m不超过100位，但用unsigned long long过了，要是完全按照题意的话就还要处理大数问题，看其它文章好像也没有很好的可以解决，就直接当unsigned long long 过了
bfs和dfs都可以，dfs注意判断不要溢出,当然由于n比较小可以先得出200个结果打表然后再过，因为可能搜索会超时，时间卡得较紧
#include<iostream>
#include<queue>
using namespace std;
int n;
typedef unsigned long long ull;
void bfs() {
queue<ull> que;
que.push(1);
while (!que.empty()) {
ull tmp = que.front();
que.pop();
if (tmp % n == 0) {
cout << tmp << endl;
return;
}
que.push(tmp * 10);
que.push(tmp * 10 + 1);
}
}
int main()
{
while (cin >> n&&n) {
bfs();
}
return 0;
}
hdu2612
题意为求两个人要到同一个@需要的最少步数乘以11.
题解
两边bfs之后将每次每一个@的步数相加，最后找出最小的那个@即可，但是要注意可能有些@是两个人都到不了的，其步数一直为0所以最后需要特殊判断一下，我legal判断x<n写成x<m了，RE了好几发━┳━ ━┳━
#include<bits/stdc++.h>
using namespace std;
vector<string> maze;
struct node {
int x, y, v;
void init(int _x, int _y) {
x = _x;
y = _y;
v = 0;
}
node(int _x, int _y) {
x = _x;
y = _y;
v = 0;
}
node() {}
};
vector<node> End;
node yifenfi, mercki;
int n, m;
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
bool legal(int x, int y, vector<string>& grid) {
return (x >= 0 && x < n&& y >= 0 && y < m&& grid[x][y] != '#');
}
void bfs(node& start) {
vector<string> grid(maze.begin(), maze.end());
int step[205][205];
memset(step, 0, sizeof(step));
queue<node> que;
grid[start.x][start.y] = '#';
que.push(start);
while (!que.empty()) {
node tmp = que.front();
que.pop();
int nx, ny;
for (int i = 0; i < 4; i++) {
nx = tmp.x + dir[i][0];
ny = tmp.y + dir[i][1];
if (legal(nx, ny, grid)) {
step[nx][ny] = step[tmp.x][tmp.y] + 1;
grid[nx][ny] = '#';
que.push(node(nx, ny));
}
}
}
for (auto& i : End) {
i.v += step[i.x][i.y];
}
}
int main() {
while (cin >> n >> m&&n>=2&&m>=2) {
string s;
maze.clear();
End.clear();
yifenfi.x = yifenfi.y = 0;
mercki.x = mercki.y = 0;
for (int i = 0; i < n; i++) {
cin >> s;
for (int j = 0; j < m; j++) {
if (s[j] == '@') {
End.push_back(node(i, j));
}
else if (s[j] == 'Y') {
yifenfi.init(i, j);
}
else if (s[j] == 'M')
mercki.init(i, j);
}
maze.push_back(s);
}
bfs(yifenfi);
bfs(mercki);
int Min = 10000;
for (auto i : End) {
if (Min > i.v&&i.v!=0) {
Min = i.v;
}
}
cout << Min * 11 << endl;
}
return 0;
}
hdu1401
题意为给定一个8 $\times$ 8的棋盘，给定四个棋子的起始坐标和终止坐标，问是否能在8步以内从起始状态到终点状态
题解
第一道双向广搜题，棋盘布局问题的一个重点是怎么查重，这就需要将每一步之后的棋盘状态给表示出来，这道题给的是一个8 $\times$ 8的棋盘，一共64个位置，因此整个棋盘的状态可以用一个long long数据来存储，64个bit位上分别可以对应棋盘上一个点是否摆放了棋子，再者还需要存储该状态是第几步得到，为了方便快速取出棋子，需要一个二维数组来存放四颗棋子的状态。中间再使用map来标记哪些状态已经到达，该map能记录每个状态需要多少步到达。
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef unsigned long long ull;
struct maze {
int chess[4][2];//棋子状态
ull hash;//每个状态独有的hash值
bool grid[8][8];//棋盘状态
}Front, Tail;//定义开始棋盘与终点棋盘
int dir1[4][2] = { {-1,0},{1,0},{0,1},{0,-1} };
int dir2[4][2] = { {-2,0},{2,0},{0,2},{0,-2} };//遇到旁边有棋子的移动步数
ull ToHash(maze& m) {
ull re = 0;
//将棋盘上每一个点的状态对应到long long 上每一个位
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
re = re << 1 | m.grid[i][j];
}
}
return re;
}
int solve(queue<maze>& que, unordered_map<ull, int>& mp1, unordered_map<ull, int>& mp2) {
//该函数相当于while循环当中的一次que.front()...que.push()...
maze tmp = que.front();
que.pop();
for (int i = 0; i < 4; i++) {
//第一重遍历，遍历四颗棋子
int x = tmp.chess[i][0], y = tmp.chess[i][1];
for (int j = 0; j < 4; j++) {
//第二重遍历，遍历四个方向
int nx = x + dir1[j][0];
int ny = y + dir1[j][1];
if (nx >= 0 && nx < 8 && ny >= 0 && ny < 8 && tmp.grid[nx][ny] == false) {//先尝试移动一步
maze next = tmp;
next.grid[nx][ny] = true;
next.grid[x][y] = false;//下一个状态里面,(x,y)已经变成了false，不用担心走回头路，因为当前棋盘的hash已经记录在map里面了
next.hash = ToHash(next);
next.chess[i][0] = nx, next.chess[i][1] = ny;
if (!mp1.count(next.hash)) {//如果变化后是以前没有的状态
mp1[next.hash] = mp1[tmp.hash] + 1;
que.push(next);
if (mp2.count(next.hash))//如果变化后与终点变过来的某一状态相同，则已经找到答案
return mp1[next.hash] + mp2[next.hash];
}
}
else if (nx >= 0 && nx < 8 && ny >= 0 && ny < 8 && tmp.grid[nx][ny] == true) {//走一步遇到了棋子
nx = x + dir2[j][0];
ny = y + dir2[j][1];
if (nx >= 0 && nx < 8 && ny >= 0 && ny < 8 && tmp.grid[nx][ny] == false) {//尝试走两步，后面代码同上
maze next = tmp;
next.grid[nx][ny] = true;
next.grid[x][y] = false;
next.hash = ToHash(next);
next.chess[i][0] = nx, next.chess[i][1] = ny;
if (!mp1.count(next.hash)) {
mp1[next.hash] = mp1[tmp.hash] + 1;
que.push(next);
if (mp2.count(next.hash))
return mp1[next.hash] + mp2[next.hash];
}
}
}
}
}
return -1;//四颗棋子遍历完发现都没有return，返回失败标记
}
int bfs() {
queue<maze> que1, que2;
que1.push(Front);
que2.push(Tail);
unordered_map<ull, int> mp1, mp2;
mp1[Front.hash] = 0;
mp2[Tail.hash] = 0;
//两个队列与map的初始化，que1代表从起始状态遍历，que2从终止状态开始，mp1和mp2分别对应两者出现过的状态
while (que1.size() && que2.size()) {
if (mp1[Front.hash] + mp2[Tail.hash] > 8)//如果两者的步数和已经超过8，返回失败
return -1;
int re;
if (que1.size() <= que2.size()) {//size小的优先，这样就能达到双端遍历的效果
re = solve(que1, mp1, mp2);
}
else
re = solve(que2, mp2, mp1);
if (re != -1 && re <= 8)
return re;
if (re > 8)
return -1;
}
return -1;
}
int main()
{
int x, y;
while (cin >> x >> y) {
x--, y--;
memset(Front.grid, false, sizeof(Front.grid));
memset(Tail.grid, false , sizeof(Tail.grid));
Front.grid[x][y] = true;
Front.chess[0][0] = x, Front.chess[0][1] = y;
for (int i = 1; i <= 3; i++) {
cin >> x >> y;
x--, y--;
Front.grid[x][y] = true;
Front.chess[i][0] = x, Front.chess[i][1] = y;
}
for (int i = 0; i < 4; i++) {
cin >> x >> y;
x--, y--;
Tail.grid[x][y] = true;
Tail.chess[i][0] = x, Tail.chess[i][1] = y;
}
Front.hash = ToHash(Front);
Tail.hash = ToHash(Tail);
if (Front.hash == Tail.hash)
cout << "YES" << endl;
else {
int re = bfs();
if (re == -1)
cout << "NO" << endl;
else
cout << "YES" << endl;
}
}
return 0;
}
hdu1495
题意是给定三个杯子，第一个被子装满水，通过这三个被子互相倒进倒出能否把水平分
题解
题目的要求是出现一个杯子为空，其它两个杯子装等量的水的情况（我第一次理解成了只要可以两个人喝到相同的水就行了，于是一边倒水一边喝，wa了老久━┳━ ━┳━)。搜索的重点就是去记录状态，这道题将三个杯子当前的装水量为一个状态进行搜索，所以开一个三维的vis[s的水量][n的水量][m的水量]bool数组来记录当前状态，每一个状态有6个方向分别是s->n,s->m,n->s,n->m,m->s,m->n(看起来代码长其实很多都是重复操作)
#include<bits/stdc++.h>
using namespace std;
#define MAXN 105
bool vis[MAXN][MAXN][MAXN];
int s, n, m;
struct node {
int s, n, m, step;
};
node start;
node re;
int bfs() {
queue<node> que;
memset(vis, false, sizeof(vis));
vis[start.s][start.n][start.m] = true;
que.push(start);
while (!que.empty()) {
node tmp = que.front();
que.pop();
if (tmp.s == 0 && tmp.m == tmp.n || tmp.m == 0 && tmp.s == tmp.n || tmp.n == 0 && tmp.s == tmp.m)
{
return tmp.step;
}
//s-->n
if (tmp.s && n > tmp.n) {//s有水并且n还没灌满
node x = tmp;
if (tmp.s > n - tmp.n) {//s的水比n现在能装的还多
x.s -= n - tmp.n;
x.n = n;
x.step += 1;
if (!vis[x.s][x.n][x.m]) {
que.push(x);
vis[x.s][x.n][x.m] = true;
}
}
else {
x.s = 0;
x.n += tmp.s;
x.step += 1;
if (!vis[x.s][x.n][x.m]) {
que.push(x);
vis[x.s][x.n][x.m] = true;
}
}
}
//s-->m
if (tmp.s && m > tmp.m) {//s有水并且m还没灌满
node x = tmp;
if (tmp.s > m - tmp.m) {//s的水比m现在能装的还多
x.s -= m - tmp.m;
x.m = m;
x.step += 1;
if (!vis[x.s][x.n][x.m]) {
que.push(x);
vis[x.s][x.n][x.m] = true;
}
}
else {
x.s = 0;
x.m += tmp.s;
x.step += 1;
if (!vis[x.s][x.n][x.m]) {
que.push(x);
vis[x.s][x.n][x.m] = true;
}
}
}
//n-->s
if (tmp.n && s > tmp.s) {//n有水并且s还没灌满
node x = tmp;
if (tmp.n > s - tmp.s) {//n的水比s现在能装的还多
x.n -= s - tmp.s;
x.s = s;
x.step += 1;
if (!vis[x.s][x.n][x.m]) {
que.push(x);
vis[x.s][x.n][x.m] = true;
}
}
else {
x.n = 0;
x.s += tmp.n;
x.step += 1;
if (!vis[x.s][x.n][x.m]) {
que.push(x);
vis[x.s][x.n][x.m] = true;
}
}
}
//n-->m
if (tmp.n && m > tmp.m) {//n有水并且m还没灌满
node x = tmp;
if (tmp.n > m - tmp.m) {//n的水比m现在能装的还多
x.n -= m - tmp.m;
x.m = m;
x.step += 1;
if (!vis[x.s][x.n][x.m]) {
que.push(x);
vis[x.s][x.n][x.m] = true;
}
}
else {
x.n = 0;
x.m += tmp.n;
x.step += 1;
if (!vis[x.s][x.n][x.m]) {
que.push(x);
vis[x.s][x.n][x.m] = true;
}
}
}
//m-->n
if (tmp.m && n > tmp.n) {//n有水并且n还没灌满
node x = tmp;
if (tmp.m > n - tmp.n) {//m的水比n现在能装的还多
x.m -= n - tmp.n;
x.n = n;
x.step += 1;
if (!vis[x.s][x.n][x.m]) {
que.push(x);
vis[x.s][x.n][x.m] = true;
}
}
else {
x.m = 0;
x.n += tmp.m;
x.step += 1;
if (!vis[x.s][x.n][x.m]) {
que.push(x);
vis[x.s][x.n][x.m] = true;
}
}
}
//m-->s
if (tmp.m && s > tmp.s) {//m有水并且s还没灌满
node x = tmp;
if (tmp.m > s - tmp.s) {//m的水比s现在能装的还多
x.m -= s - tmp.s;
x.s = s;
x.step += 1;
if (!vis[x.s][x.n][x.m]) {
que.push(x);
vis[x.s][x.n][x.m] = true;
}
}
else {
x.m = 0;
x.s += tmp.m;
x.step += 1;
if (!vis[x.s][x.n][x.m]) {
que.push(x);
vis[x.s][x.n][x.m] = true;
}
}
}
}
return 0;
}
int main()
{
while (cin >> s >> n >> m) {
if (s == n && n == m && s == 0)
break;
start.s = s, start.n = 0, start.m = 0;
start.step = 0;
if (s & 1) {
cout << "NO" << endl;
}
else {
int re = bfs();
if (re) {
cout << re << endl;
}
else
cout << "NO" << endl;
}
}
return 0;
}
2021.7.19
题意是给定一个起始的四位的素数和目标四位的素数，每一步可以变动一个位置上的数字，要求变动之后数字还是素数，且还是要四位数，求最少步数。
题解
最近做这个专题发现基本上都是问最少步数，也基本上都是bfs,这道题的状态可以直接由一个数字本身确定，由于范围较小，可以提前将所有的四位素数计算出来，方便后面判断。代码如下
#include<iostream>
#include<queue>
#include<map>
using namespace std;
bool prime[100000];//判断素数
int main()
{
for (int i = 2; i < 100000; i++) {
if (!prime[i]) {
for (int j = 2; j * i < 100000; j++) {
prime[i * j] = true;
}
}
}//埃氏筛
int t, a, b;
cin >> t;
bool flag = false;
while (t--) {
cin >> a >> b;
queue<int>que;
map<int, int> mp;//bfs的标记数组，mp[1000]=1表示1000y
mp[a] = 0;
que.push(a);
while (!que.empty()) {
int tmp = que.front();
que.pop();
if (tmp == b) {
flag = true;
break;
}
//下面四个for循环分别对应修改四个位置上的数字
for (int i = 0; i < 10; i++) {
int num = tmp % 1000 + i * 1000;
if (!prime[num] && mp.count(num) == 0&&num>1000) {
mp[num] = mp[tmp] + 1;
que.push(num);
}
}
for (int i = 0; i < 10; i++) {
int num = tmp - ((tmp / 100) % 10) * 100 + i * 100;
if (!prime[num] && mp.count(num) == 0&&num>1000) {
mp[num] = mp[tmp] + 1;
que.push(num);
}
}
for (int i = 0; i < 10; i++) {
int num = tmp - ((tmp / 10) % 10) * 10 + i * 10;
if (!prime[num] && mp.count(num) == 0&&num>1000) {
mp[num] = mp[tmp] + 1;
que.push(num);
}
}
for (int i = 0; i < 10; i++) {
int num = tmp -(tmp%10) + i;
if (!prime[num] && mp.count(num) == 0&&num>1000) {
mp[num] = mp[tmp] + 1;
que.push(num);
}
}
}
if (flag)
cout << mp[b]<<endl;
else
cout << "impossible" << endl;
}
return 0;
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 2128099421@qq.com
