kuangbin搜索入门

自用笔记算法

kaungbin搜索入门

poj 1321

题目要求

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。
输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中#表示棋盘区域，.表示空白区域（数据保证不出现多余的空白行或者空白列）。
对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
#include<cstring>
using namespace std;
int n,k,ans,num;
char mp[10][10];
int vis[10];
void dfs(int cur){
	if(num==k){
		ans++;
		return;
	}
	if(cur==n) return;
	for(int i=0;i<n;i++){
		if(mp[cur][i]=='.') continue;
		if(!vis[i]){
			vis[i]=1;
			num++;
			dfs(cur+1);
			vis[i]=0;
			num--;
		}
	}
	dfs(cur+1);
}
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d",&n,&k)!=EOF){
		if(n==-1 && k==-1) break;
		for(int i=0;i<n;i++) scanf("%s",mp[i]);
		ans=0,num=0;
		memset(vis,0,sizeof(vis));
		dfs(0);
		printf("%d\n",ans);
	}
	return 0;
}

思路

相当于八皇后的回溯 这里不考虑对角线 一维vis即可
加了一个k的限制 num统计加入的棋子个数 当num==k时更新答案
注意最后还要dfs(cur+1)
这里跟八皇后不同 因为本题不确保可以从上一行正确进入下一行 所以必须手加这句话

poj 2251

题目要求

三维空间从s到t的最短移动次数
.代表可以走 #代表不能走

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 35
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int num,n,m,ans;
int sx,sy,sz,ex,ey,ez;
char mp[maxn][maxn][maxn];
int vis[maxn][maxn][maxn];
int dirx[6]={-1,0,0,1,0,0};
int diry[6]={0,-1,0,0,1,0};
int dirz[6]={0,0,-1,0,0,1};
struct node{
	int x,y,z,time;
};
bool check(int x,int y,int z){
	if(x<1 || x>num) return true;
	if(y<1 || y>n) return true;
	if(z<1 || z>m) return true;
	if(mp[x][y][z]=='#') return true;
	return false;
}
void bfs(){
	queue<node>Q;
	node a;
	a.x=sx,a.y=sy,a.z=sz,a.time=0;
	Q.push(a);
	while(!Q.empty()){
		node b=Q.front();
		Q.pop();
		if(b.x==ex && b.y==ey && b.z==ez){
			ans=b.time;
			break;
		}
		if(check(b.x,b.y,b.z)) continue;
		if(vis[b.x][b.y][b.z]) continue;
		vis[b.x][b.y][b.z]=1;
		for(int i=0;i<6;i++){
			int nextx=b.x+dirx[i];
			int nexty=b.y+diry[i];
			int nextz=b.z+dirz[i];
			node tmp;
			tmp.x=nextx,tmp.y=nexty,tmp.z=nextz,tmp.time=b.time+1;
			Q.push(tmp);
		}
	}
}
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d%d",&num,&n,&m)!=EOF){
		if(n==0 && m==0 && num==0) break;
		for(int i=1;i<=num;i++){
			for(int j=1;j<=n;j++) scanf("%s",mp[i][j]+1);
			for(int j=1;j<=n;j++){
				for(int k=1;k<=m;k++){
					if(mp[i][j][k]=='S'){
						sx=i,sy=j,sz=k;
					}
					if(mp[i][j][k]=='E'){
						ex=i,ey=j,ez=k;
					}
				}
			}
		}
		ans=0;
		mm(vis,0);
		bfs();
		if(ans==0) puts("Trapped!");
		else printf("Escaped in %d minute(s).\n",ans);
	}
	return 0;
}

思路

三维宽搜

poj 3278

题目要求

一条线段 问从s到t的最短移动单位时间
每次移动要遵循：pos+1，pos-1，2×pos 三种

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,m,ans;
int vis[100050];
struct node{
	int pos,step;
};
bool check(int pos){
	if(pos<0 || pos>100000) return true;
	return false;
}
void bfs(){
	queue<node>Q;
	node a;
	a.pos=n,a.step=0;
	Q.push(a);
	while(!Q.empty()){
		node b=Q.front();
		Q.pop();
		if(b.pos==m){
			ans=b.step;
			break;
		}
		if(check(b.pos)) continue;
		if(vis[b.pos]) continue;
		vis[b.pos]=1;
		node x1,x2,x3;
		x1.pos=b.pos+1,x1.step=b.step+1;
		x2.pos=b.pos-1,x2.step=b.step+1;
		x3.pos=2*b.pos,x3.step=b.step+1;
		Q.push(x1),Q.push(x2),Q.push(x3);
	}
}
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d",&n,&m)!=EOF){
		ans=0;
		memset(vis,0,sizeof(vis));
		if(n>m) printf("%d\n",n-m);
		else{
			bfs();
			printf("%d\n",ans);
		}
	}
	return 0;
}

思路

宽搜

poj 3279

题目要求

有一个01矩阵 目标是用最少的转换次数把它变成全0矩阵
转换方法：每次可以把一个位置的1变成0 0变成1 上下左右四个位置也要转置

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
#define maxn 20
using namespace std;
const int inf = 0x3f3f3f3f;
const int dx[]={-1,0,1,0,0};
const int dy[]={0,-1,0,1,0};
int grid[maxn][maxn],state[maxn][maxn],tmp[maxn][maxn],rec[maxn][maxn];
int n, m, ans;
void flip(int x,int y){
    tmp[x][y]=1;
    int nx,ny;
    for(int i=0;i<5;i++){
        nx=x+dx[i];
        ny=y+dy[i];
        state[nx][ny]=!state[nx][ny];
    }
}
bool isEmpty(int n){
    for(int j=1;j<=m;j++) {
        if(state[n][j]) return false;
    }
    return true;
}
void solve(int st){
    memcpy(state,grid,sizeof(grid));
    memset(tmp,0,sizeof(tmp));
    int cnt=0;
    for(int j=0;j<m;j++){
        if((st>>j)&1) {
            flip(1,j+1);
            cnt++;
        }
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(state[i-1][j]==1){
                flip(i,j);
                cnt++;
            }
        }
    }
    if(isEmpty(n) && cnt<ans){
        ans=cnt;
        memcpy(rec,tmp,sizeof(tmp));
    }
}
int main(){
//	freopen("input.txt","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++) scanf("%d",&grid[i][j]);
        }
        ans=inf;
        int end=1<<m;
        for(int st=0;st<end;st++) solve(st);
        if(ans==inf) puts("IMPOSSIBLE");
        else{
            for(int i=1;i<=n;i++){
            	for(int j=1;j<=m;j++){
            		if(j==m) printf("%d\n",rec[i][j]);
					else printf("%d ",rec[i][j]); 	
				}
            }
        }
    }
    return 0;
}

思路

跟uva11464(白书P15)类似 状压+枚举计算
由于n是15 所以可以用二进制枚举第一行的状态
然后通过题目的限制条件来计算下面每一行
如果上一行是1的话 那么下面一行肯定要翻转 因为只有下面一行能影响上面一行
最后判断一下 最后一行是不是都是0 如果都是 则维护最小的翻转次数

poj 1426

题目要求

给定一个小于200的正整数n 求出任意一个n的倍数 并且它的十进制表示法只由0和1组成

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<cstdio>
#include<queue>
#define LL long long
using namespace std;
int n;
void bfs(){
	queue<LL>Q;
	Q.push(1);
	while(!Q.empty()){
		LL x=Q.front();
		Q.pop();
		if(x%n==0){
			printf("%lld\n",x);
			break;
		}
		Q.push(x*10);
		Q.push(x*10+1);
	}
} 
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d",&n)!=EOF){
		if(n==0) break;
		bfs();
	}
	return 0;
}

思路

本题有一个结论 小于200的倍数最多在18位内肯定存在 所以开LL即可不需要大数
也可以用dfs 给定一个位数的上限即可
bfs直接暴力搜×10 和×10+1

本文标题:kuangbin搜索入门

文章作者:Hippopmonkey

发布时间:2017-11-28, 15:38:35

最后更新:2017-12-08, 11:50:34

原始链接:http://xuboming8.github.io/2017/11/28/搜索入门/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. kaungbin搜索入门
    1. 1.1. poj 1321
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. poj 2251
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. poj 3278
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. poj 3279
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. poj 1426
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
|