简单搜索小题狂练

kuangbin带你飞专题一

http://poj.org/problem?id=1321

深搜一遍

 1 #include<stdio.h>
 2 #include<string.h>
 3 char mp[10][10],flag[10];
 4 int n,m,ans;
 5 
 6 void dfs(int x,int an9)
 7 {
 8     if(an9==m){
 9         ans++;
10         return ;
11     }
12     for(int i=x;i<n;i++){
13         for(int j=0;j<n;j++){
14             if(mp[i][j]=='#'&&flag[j]==0){
15                 flag[j]=1;
16                 dfs(i+1,an9+1);
17                 flag[j]=0;
18             }
19         }
20     }
21 }
22 int main()
23 {
24     //freopen( "in.txt", "r", stdin);
25     while( ~scanf("%d%d",&n,&m)){
26         if(n==-1&&m==-1) break;
27         for(int i=0;i<n;i++)
28             scanf("%s",mp[i]);
29         ans=0;
30         memset( flag, 0, sizeof flag);
31         for(int i=0;i<n;i++){
32             for(int j=0;j<n;j++){
33                 if(mp[i][j]=='#'){
34                     flag[j]=1;
35                     dfs(i+1,1);
36                     flag[j]=0;
37                 }
38             }
39         }
40         printf("%d
",ans);
41     }
42     return 0;
43 }

View Code

http://poj.org/problem?id=2251

广搜一遍（代码后面再改改）

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<queue>
  4 #include<algorithm>
  5 using namespace std;
  6 #define Max 36
  7 char mp[Max][Max][Max];
  8 int L,R,C,ans,ex,ey,ez;
  9 int moz[]={0,0,0,0,1,-1};
 10 int moy[]={0,0,1,-1,0,0};
 11 int mox[]={1,-1,0,0,0,0};
 12 int flag[Max][Max][Max];
 13 
 14 bool cheat(int x, int y, int z)
 15 {
 16     if(x>0&&y>0&&z>0&&x<=L&&y<=R&&z<=C&&flag[x][y][z]==0&&(mp[x][y][z]=='.'||mp[x][y][z]=='E')){
 17         return true;
 18     }
 19     return false;
 20 }
 21 typedef struct P{int x,y,z;};
 22 void bfs(int opx,int opy,int opz,int anp)
 23 {
 24     queue<P> op;
 25     P p,q;
 26     p.x=opx,p.y=opy,p.z=opz;
 27     flag[opx][opy][opz]=1;
 28     op.push(p);
 29     while(!op.empty()){
 30         int tim=op.size();
 31         p=op.front();
 32         op.pop();
 33         if(mp[p.x][p.y][p.z]=='E'){
 34             ans=anp;
 35             break;
 36         }
 37         for(int i=0;i<6;i++){
 38             int x,y,z;
 39             x=p.x+mox[i];
 40             y=p.y+moy[i];
 41             z=p.z+moz[i];
 42             if(cheat(x,y,z)){
 43                 flag[x][y][z]=1;
 44                 q.x=x;
 45                 q.y=y;
 46                 q.z=z;
 47                 op.push(q);
 48             }
 49         }
 50         while(--tim){
 51             p=op.front();
 52             op.pop();
 53             if(mp[p.x][p.y][p.z]=='E'){
 54                 ans=anp;
 55                 break;
 56             }
 57             for(int i=0;i<6;i++){
 58                 int x,y,z;
 59                 x=p.x+mox[i];
 60                 y=p.y+moy[i];
 61                 z=p.z+moz[i];
 62                 if(cheat(x,y,z)){
 63                     flag[x][y][z]=1;
 64                     q.x=x;
 65                     q.y=y;
 66                     q.z=z;
 67                     op.push(q);
 68                 }
 69             }
 70         }
 71         anp++;
 72     }
 73 }
 74 
 75 int main()
 76 {
 77 //    freopen( "in.txt", "r", stdin);
 78     while( ~scanf("%d%d%d",&L,&R,&C)){
 79         if(L==0&&R==0&&C==0) break;
 80         int bx,by,bz;
 81         memset( flag, 0, sizeof flag);
 82         for(int i=1;i<=L;i++){
 83             getchar();
 84             for(int j=1;j<=R;j++){
 85                 for(int k=1;k<=C;k++){
 86                     scanf("%c",&mp[i][j][k]);
 87                     if(mp[i][j][k]=='S'){
 88                         bx=i,by=j,bz=k;
 89                     }
 90                     if(mp[i][j][k]=='E'){
 91                         ex=i,ey=j,ez=k;
 92                     }
 93                 }
 94                 getchar();
 95             }
 96         }
 97 //        printf("%d %d %d
",ex,ey,ez);
 98         ans=1e7;
 99         bfs(bx,by,bz,0);
100         if(ans!=1e7){
101             printf("Escaped in %d minute(s).
",ans);
102         }
103         else{
104             printf("Trapped!
");
105         }
106     }
107     return 0;
108 }

View Code

http://poj.org/problem?id=3278

广搜

 1 #include<stdio.h>
 2 #include<math.h>
 3 #include<string.h>
 4 #include<stdlib.h>
 5 #include<queue>
 6 using namespace std;
 7 #define Max 100006
 8 using namespace std;
 9 int n,en,ans;
10 int flag[Max];
11 
12 void bfs(int op)
13 {
14     queue<int> q;
15     q.push(op);
16     flag[op]=1;
17     int fi=0;
18     while(!q.empty()){
19         int iop,num;
20         num=q.size();
21         while(num--){
22             iop=q.front();
23             q.pop();
24             int x,y,z;
25             x=iop+1;
26             y=iop*2;
27             z=iop-1;
28             if(x==en||y==en||z==en){
29                 fi=1;
30                 break;
31             }
32             if(!flag[x]){
33                 q.push(x);
34                 flag[x]=1;
35             }
36             if(y<Max&&!flag[y]){
37                 q.push(y);
38                 flag[y]=1;
39             }
40             if(z>0&&!flag[z]){
41                 q.push(z);
42                 flag[z]=1;
43             }
44         }
45         ans++;
46         if(fi==1)
47             break;
48     }
49 }
50 
51 int main()
52 {
53     while( ~scanf("%d%d",&n,&en)){
54         memset( flag, 0, sizeof flag);
55         if(n>=en){
56             printf("%d
",n-en);
57             continue;
58         }
59         ans=0;
60         bfs(n);
61         printf("%d
",ans);
62     }
63     return 0;
64 }

View Code

http://poj.org/problem?id=1426

题意：要求找出n的倍数，并且只含有0/1.

思路：从1开始进行广搜，每次入队*10与*10+1，遇到%n==0时结束搜索。

注意大数，因此用longlong。

 1 #include<cstdio>
 2 #include<queue>
 3 #define ll long long
 4 using namespace std;
 5 int n;
 6 
 7 void bfs()
 8 {
 9     queue<ll> op;
10     op.push(1);
11     int k=1;
12     ll ans=0;
13     for(int i=1;;i++){
14         for(int j=1;j<=k;j++){
15             ans=op.front();
16             op.pop();
17             if(ans%n==0){
18                 printf("%lld
",ans);
19                 return ;
20             }
21             ans *=10;
22             op.push(ans); op.push(ans+1);
23         }
24         k*=2;
25     }
26 }
27 
28 int main()
29 {
30     while( ~scanf("%d",&n)){
31         if(!n) break;
32         bfs();
33     }
34     return 0;
35 }

View Code

http://poj.org/problem?id=3126

题意：输入两个数，n，m。都是四位数，要求从n到m，而且每次变化都要是素数。

思路：把1000到10000的素数存进set，把每一位数提取出来，逐一变化。

发现素数不会找，上网查了一下筛法求素数，惭愧qwq。貌似还有更加简便的sprintf.........

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<set>
 4 #include<queue>
 5 using namespace std;
 6 const int maxm=10006;
 7 set<int> prime;
 8 bool num[maxm],flag[maxm];
 9 int fir[5];
10 
11 void pri()
12 {
13     prime.clear();
14     memset( num, false, sizeof num);
15     num[0]=num[1]=1;
16     for(int i=2;i<maxm;i++){
17         if(!num[i]){
18             prime.insert(i);
19             for(int j=i*2;j<maxm;j+=i){
20                 num[j]=1;
21             }
22         }
23     }
24 }
25 
26 int pow(int one,int two)
27 {
28     int ans=1;
29     for(int i=1;i<=two;i++){
30         ans*=one;
31     }
32     return ans;
33 }
34 
35 void bfs(int beg,int bec)
36 {
37     memset(flag, false, sizeof flag);
38 //    printf("%d
",prime.size());
39     flag[beg]=true;
40     int ans=0;
41     queue<int> way;
42     way.push(beg);
43     while(!way.empty()){
44         int bigw=way.size();
45 //        printf("size=%d
",bigw);
46         for(int jkl=1;jkl<=bigw;jkl++){
47             int a=way.front();
48             way.pop();
49             if(a==bec){
50                 printf("%d
",ans);
51 //                printf("%d",a);
52                 return ;
53             }
54             for(int i=1;i<=4;i++){
55                 int mid1=pow(10,4-i);
56                 fir[i]=(a/mid1)%10;
57             }
58             for(int j=1;j<=4;j++){
59                 for(int k=0;k<=9;k++){
60                     if(j==1&&k==0)
61                         continue;
62                     int cheat=0;
63                     for(int op=1;op<=4;op++){
64                         if(op==j){
65                             cheat+=k*pow(10,4-op);
66                             continue;
67                         }
68                         cheat+=fir[op]*pow(10,4-op);
69                     }
70                     if(prime.count(cheat)&&!flag[cheat]){
71                         flag[cheat]=true;
72                         way.push(cheat);
73 //                        printf("%d ",cheat);
74                     }
75                 }
76             }
77 //            printf("
");
78         }
79         ans++;
80     }
81 }
82 
83 int main()
84 {
85     int N;
86     pri();
87 //    printf("%d
",prime.size());
88     while( ~scanf("%d",&N)){
89         while(N--){
90             int a,b;
91             scanf("%d%d",&a,&b);
92             bfs(a,b);
93         }
94     }
95     return 0;
96 }

View Code

Problem Description

Fat brother and Maze are playing a kind of special (hentai) game on an N*M board (N rows, M columns). At the beginning, each grid of this board is consisting of grass or just empty and then they start to fire all the grass. Firstly they choose two grids which are consisting of grass and set fire. As we all know, the fire can spread among the grass. If the grid (x, y) is firing at time t, the grid which is adjacent to this grid will fire at time t+1 which refers to the grid (x+1, y), (x-1, y), (x, y+1), (x, y-1). This process ends when no new grid get fire. If then all the grid which are consisting of grass is get fired, Fat brother and Maze will stand in the middle of the grid and playing a MORE special (hentai) game. (Maybe it’s the OOXX game which decrypted in the last problem, who knows.)

You can assume that the grass in the board would never burn out and the empty grid would never get fire.

Note that the two grids they choose can be the same.

Input

The first line of the date is an integer T, which is the number of the text cases.

Then T cases follow, each case contains two integers N and M indicate the size of the board. Then goes N line, each line with M character shows the board. “#” Indicates the grass. You can assume that there is at least one grid which is consisting of grass in the board.

1 <= T <=100, 1 <= n <=10, 1 <= m <=10

Output

For each case, output the case number first, if they can play the MORE special (hentai) game (fire all the grass), output the minimal time they need to wait after they set fire, otherwise just output -1. See the sample input and output for more details.

Sample Input

4
3 3
.#.
###
.#.
3 3
.#.
#.#
.#.
3 3
...
#.#
...
3 3
###
..#
#.#

Sample Output

Case 1: 1
Case 2: -1
Case 3: 0
Case 4: 2

题意：两个人点火玩，每人最多点一次火，要求把‘#’的草全部烧毁，点燃一处后火势可以向上下左右蔓延没扩散一次时间就加一，要求求出最短的时间是多少，若无结果则输出-1。

思路：我的思路是用dfs先看一下，是否只有两堆或以下的草堆。若超过二，则输出-1.

然后用bfs遍历找最少的时间。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<queue>
  5 #define inf 0x3f3f3f
  6 using namespace std;
  7 
  8 int n,m,ans;
  9 int flag[16][16];
 10 int dis[16][16];
 11 char mp[16][16];
 12 int mox[4]={0,0,1,-1}, moy[4]={1,-1,0,0};
 13 struct xy{int x,y;};
 14 
 15 void dfs(int x,int y)
 16 {
 17     flag[x][y]=1;
 18     int opx,opy;
 19     for(int i=0;i<4;i++){
 20         opx=x+mox[i];
 21         opy=y+moy[i];
 22         if(opx>=0&&opx<n&&opy>=0&&opy<m&&mp[opx][opy]=='#'&&!flag[opx][opy]){
 23             flag[opx][opy]=1;
 24             dfs(opx,opy);
 25         }
 26     }
 27 }
 28 
 29 int bfs(int x1,int y1,int x2,int y2)
 30 {
 31     queue<xy> iop;
 32     xy dop1,dop2;
 33     dop1.x=x1; dop1.y=y1;
 34     dop2.x=x2; dop2.y=y2;
 35     iop.push(dop1);
 36     iop.push(dop2);
 37     memset( dis, inf, sizeof dis);
 38     int rem=0;
 39     dis[x1][y1]=0;
 40     dis[x2][y2]=0;
 41     while(!iop.empty()){
 42         dop1=iop.front();
 43         iop.pop();
 44         for(int i=0;i<4;i++){
 45             int xx,yy;
 46             xx=dop1.x+mox[i];
 47             yy=dop1.y+moy[i];
 48             if(xx>=0&&xx<n&&yy>=0&&yy<m&&mp[xx][yy]=='#'&&dis[xx][yy]>dis[dop1.x][dop1.y]+1){
 49                 dis[xx][yy]=dis[dop1.x][dop1.y]+1;
 50                 dop2.x=xx;
 51                 dop2.y=yy;
 52                 iop.push(dop2);
 53             }
 54         }
 55     }
 56     rem=0;
 57     for(int i=0;i<n;i++)
 58     for(int j=0;j<m;j++)
 59     if(mp[i][j]=='#')
 60         rem=max(rem,dis[i][j]);///若没有烧完两堆着rem为inf，此处代码核心。
 61 
 62     return rem;
 63 }
 64 
 65 int main()
 66 {
 67     int T;
 68     scanf("%d",&T);
 69     for(int cas=1;cas<=T;cas++){
 70         scanf("%d%d",&n,&m);
 71         for(int i=0;i<n;i++)
 72             scanf("%s",mp[i]);
 73 
 74         int cha=0;
 75         memset( flag, 0, sizeof flag);
 76         for(int i=0;i<n&&cha<=2;i++){
 77             for(int j=0;j<m&&cha<=2;j++){
 78                 if(mp[i][j]=='#'&&flag[i][j]==0){
 79                     flag[i][j]=1;
 80                     dfs(i,j);
 81                     cha++;
 82                 }
 83             }
 84         }   ///dfs找草堆的操作
 85         if(cha>2){
 86             printf("Case %d: -1
",cas);
 87             continue;
 88         }
 89 
 90         ans=inf;
 91         for(int i=0;i<n;i++)
 92         for(int j=0;j<m;j++)
 93         if(mp[i][j]=='#') ///用bfs搜两遍意为两个人点火。
 94         for(int ii=i;ii<n;ii++)
 95         for(int jj=0;jj<m;jj++)
 96         if(mp[ii][jj]=='#'){
 97             int temp;
 98             temp=bfs(i,j,ii,jj);
 99             ans=min(ans,temp);
100         }
101 
102         if(ans==inf)
103             ans=-1;
104         printf("Case %d: %d
",cas,ans);
105     }
106     return 0;
107 }

View Code