pyai's blog
0%

专题一 简单搜索

Posted on Edited on In Views:

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
32
#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