0%

专题一 简单搜索

POJ 1321 棋盘问题

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
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
char mp[10][10];
int ans=0,vis[10],n,k;
void dfs(int x,int cnt){
if(cnt==k){
ans++;return ;
}
for(int i=x;i<n;i++){
for(int j=0;j<n;j++){
if(mp[i][j]=='#'&&!vis[j]){
vis[j]=1;
dfs(i+1,cnt+1);
vis[j]=0;
}
}
}
}
int main()
{
while(cin>>n>>k){
if(n==-1&&k==-1) break;
ans=0;
memset(vis,0,sizeof vis);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>mp[i][j];
}
}
dfs(0,0);
cout<<ans<<"\n";
}
}

POJ 2251 Dungeon Master

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
74
75
76
77
78
79
#include<iostream>
#include<map>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<climits>
#include<algorithm>
#include<cmath>
#include<climits>
#include<queue>
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
const int maxn=30;
string mp[maxn][maxn];//mp[l][r];
int vis[maxn][maxn][maxn];
int dir[6][3]={{0,-1,0},{0,1,0},{0,0,-1},{0,0,1},{1,0,0},{-1,0,0}};
int L,R,C,Sl,Sr,Sc,Tl,Tr,Tc;
int ans=INT_MAX;
struct Node{
int l,r,c,cnt;
};
bool is_ok(int l,int r,int c){
return (l>=0&&l<L&&r>=0&&r<R&&c>=0&&c<C&&(mp[l][r][c]=='E'||mp[l][r][c]=='.')&&!vis[l][r][c]);
}
void bfs(int l,int r,int c,int cnt){
queue<Node>qu;
qu.push({l,r,c,cnt});
while(!qu.empty()){
Node node=qu.front();
qu.pop();
l= node.l;r=node.r;c=node.c;cnt=node.cnt;
for(int i=0;i<6;i++){
int next_l=l+dir[i][0];
int next_r=r+dir[i][1];
int next_c=c+dir[i][2];
if(is_ok(next_l,next_r,next_c)){
vis[next_l][next_r][next_c]=1;
qu.push({next_l,next_r,next_c,cnt+1});
if(next_l==Tl&&next_r==Tr&&next_c==Tc){
ans=cnt+1;
return ;
}
}
}
}

return ;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
while(cin>>L>>R>>C&&L&&R&&C){
memset(vis,0,sizeof vis);
ans=INT_MAX;
for(int i=0;i<L;i++){
for(int j=0;j<R;j++){
cin>>mp[i][j];
for(int k=0;k<C;k++){
if(mp[i][j][k]=='S'){
Sl=i;Sr=j;Sc=k;
}else if(mp[i][j][k]=='E'){
Tl=i;Tr=j;Tc=k;
}
}
}
}
vis[Sl][Sr][Sc]=1;
bfs(Sl,Sr,Sc,0);
if(ans==INT_MAX){
cout<<"Trapped!\n";
}else{
cout<<"Escaped in "<<ans<<" minute(s).\n";
}
}

return 0;
}

POJ 3278 Catch That Cow

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
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=100001;
bool vis[maxn];
int n,k;
struct Node {
int x,step;
};
Node q[maxn];
int bfs() {
int i;
Node now,next;
int head,tail;
head=tail=0;
q[tail].x=n;
q[tail].step=0;
tail++;
vis[n]=true;
while(head<tail) {
now=q[head];//取队首
head++;//弹出对首
for(i=0; i<3; i++) {
if(i==0) next.x=now.x-1;
else if(i==1) next.x=now.x+1;
else next.x=2*now.x;
if(next.x<0 || next.x>=maxn) continue;//剪枝、排除越界
if(!vis[next.x]) {
vis[next.x]=true;
next.step=now.step+1;
q[tail].x=next.x;
q[tail].step=next.step;
tail++;
if(next.x==k) return next.step;
}
}
}
}
int main() {
while(cin>>n>>k) {
memset(vis,false,sizeof(vis));
if(n>=k) cout<<n-k<<endl;
else cout<<bfs()<<endl;
}
return 0;
}

POJ 3279 Fliptile

首先是一个状压DP,状压DP就是用用数字来保存一系列对象的状态,如本题中枚举第一行的所有状态的代码,枚举完第一行后就可以从第二行开始计算了,此时第一行的状态只能由第二行改变,所以要用get_color(i-1,j)来获得上面那个点的状态,而上面那个点的状态目前由mp[i][j]^tmp[i][j]^tmp[i-1][j]^tmp[i][j-1]^tmp[i][j+1]来决定,依次类推可以获得最后一行的状态,如果全是0,就返回这个结果,最终取最优解。时间复杂度$O(2^nmn)$

代码如下:

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
#include<iostream>
#include<cmath>
#include<cstring>
#define LL long long
using namespace std;
const int M=15+10;
const int N=15+10;
const int INF=0x3f3f3f3f;
int mp[M][N],tmp[M][N],ans[M][N],m,n;
int get_color(int i,int j){
return (mp[i][j]^tmp[i][j]^tmp[i-1][j]^tmp[i][j-1]^tmp[i][j+1]);
}
int solve(int cur_cnt){
int cnt=cur_cnt;
for(int i=2;i<=m+1;i++){
for(int j=1;j<=n;j++){
tmp[i][j]=get_color(i-1,j);
cnt+=tmp[i][j];
}
}
for(int i=1;i<=n;i++){
if(tmp[m+1][i]) return INF;
}
return cnt;
}
int main(){
cin>>m>>n;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cin>>mp[i][j];
}
}
int sum=INF;
for(int i=0;i<(1<<n);i++){//枚举第一行的所有可能
memset(tmp,0,sizeof tmp);
int cur_cnt=0;
for(int j=1;j<=n;j++){//生成第一行的操作
cur_cnt+=tmp[1][j]=(1&(i>>(n-j)));
}
int cur=solve(cur_cnt);
if(cur<sum){//当前结果更优
memcpy(ans,tmp,sizeof tmp);//将结果保存到ans数组
sum=cur;
}
}
if(sum==INF) cout<<"IMPOSSIBLE";
else{
//cout<<"sum:"<<sum<<endl;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cout<<ans[i][j]<<" ";
}
cout<<endl;
}
}
return 0;
}

POJ 1426 Find The Multiple

首先这题从高位向低位搜索。

根据手算除法可以知道,我们都是从高位开始除,如果高位对n没整除,那么就把余数乘10加到下一位,再加上完全二叉树(根节点为1)的规律列出下面的状态转移方程。

$$
dp[i\times2]=dp[i]\times10 \mod n \\
dp[i\times2+1]=(dp[i]+1)\times10\mod n
$$
代码如下:

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
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#define LL long long
using namespace std;
LL n;
int dp[1<<20];
vector<int>ans;
//dp[i]存储从根节点到i形成的十进制数对n的余数
//for i in range(i:~)模拟对完全二叉树的层次遍历,i代表第几个节点,也就是在完全二叉树走过的路径对应的十进制数。
//
int main() {
while(cin>>n&&n) {
dp[1]=1;
int now;
for(int i=1;; i++) {
if(!(dp[i*2]=(dp[i]*10)%n)) {
now=i*2;
break;
}
if(!(dp[i*2+1]=(dp[i]*10+1)%n)) {
now=i*2+1;
break;
}
}
ans.clear();
while(now) {
ans.push_back(now%2);
now/=2;
}
for(int i=ans.size()-1;i>=0; i--) {
cout<<ans[i];
}
cout<<endl;
}
return 0;
}

POJ 3126 Prime Path

就是先打素数表,然后从给的第一个数开始bfs,用vis数组标记一下已经bfs到的素数,直到bfs到给的第二个素数,结束bfs,输出bfs次数cnt

代码如下:

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
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#define LL long long
using namespace std;
const int maxn=1e5+10;
int prime[maxn];
void get_prime(){
memset(prime,0,sizeof prime);
prime[0]=prime[1]=1;
for(LL i=2;i<maxn;i++) if(!prime[i]){
for(LL j=i*i;j<maxn;j+=i) prime[j]=1;
}
return;
}
struct Node{
int num;
int cnt;
Node(int num,int cnt=0):num(num),cnt(cnt){}
};
int vis[maxn];
int bfs(int s,int t){
memset(vis,0,sizeof vis);
Node node=Node(s,0);
queue<Node>qu;
qu.push(node);
int num,cnt;
while(!qu.empty()){
node=qu.front();
qu.pop();
num=node.num;
vis[num]=1;
cnt=node.cnt;
if(num==t) break;
int ctl=1000;
while(ctl){
for(int i=0;i<10;i++){
int tmp=num;
if(ctl==1000&&i==0) continue;
tmp=((10*ctl)*(tmp/(10*ctl))+tmp%ctl+i*ctl);
if(!prime[tmp]&&!vis[tmp]) qu.push(Node(tmp,cnt+1));
}
ctl/=10;
}
}
return cnt;
}
int main(){
get_prime();
int t,a,b;
cin>>t;
while(t--){
cin>>a>>b;
cout<<bfs(a,b)<<endl;
}
return 0;
}

POJ 3087 Shuffle’m Up

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
string s1, s2, s12, new_s12 = "";
int N, C;
int main(){
cin >> N;
int cnt = 1;
while(N--){
map<string, bool>mp;
int flag = 0, num = 0;
cin >> C >> s1 >> s2 >> s12;
while(new_s12 != s12){
new_s12 = "";
for(int i=0; i<C;i++){
new_s12 += s2[i]; new_s12 += s1[i];
}
new_s12 += "\0";
if(mp[new_s12]){
flag = 1; break;
}else mp[new_s12] = true;
num++;
s1 = new_s12.substr(0,C); s2 = new_s12.substr(C,C);
}
cout << cnt++ << " " << (flag?-1:num) << "\n";
}
return 0;
}

POJ 3414 Pots

FZU 2150 Fire Game

UVA 11624 Fire!

POJ 3984 迷宫问题

HDU 1241 Oil Deposits

HDU 1495 非常可乐

HDU 2612 Find a way

如果对您有帮助,请我喝杯奶茶?