搜索专题(不定期更新)-白红宇

搜索专题(不定期更新)

阅读量：6037 次

发布时间：2019-06-20

本文共 54029 字，大约阅读时间需要 180 分钟。

1、

　　题意：给出一块区域，询问有多少个湖泊？

　　思路：DFS，对于‘W’，深搜一次，并标记已访问。之后每次对未访问的‘W’做一次深搜。

1 #include
      
        2 #include
       
         3 using namespace std; 4 char lake[105][105]; 5 bool vis[105][105]; 6 int n, m; 7 void DFS(int r, int c) 8 { 9     if (r >=n || r<0 || c>=m || c < 0) return;10     if (lake[r][c] == 'W'&&!vis[r][c])11     {12         vis[r][c] = true;13         DFS(r + 1, c);14         DFS(r - 1, c);15         DFS(r, c + 1);16         DFS(r, c - 1);17         DFS(r + 1, c + 1);18         DFS(r + 1, c - 1);19         DFS(r - 1, c + 1);20         DFS(r - 1, c - 1);21     }22 }23 int main()24 {25     while (cin >> n >> m)26     {27         memset(lake, 0, sizeof(lake));28         memset(vis, 0, sizeof(vis));29         for (int i = 0; i < n; i++)30         {31             for (int j = 0; j < m; j++)32             {33                 cin >> lake[i][j];34             }35         }36         int num = 0;37         for (int i = 0; i < n; i++)38         {39             for (int j = 0; j < m; j++)40             {41                 if (lake[i][j] == 'W' && !vis[i][j])42                 {43                     DFS(i, j);44                     num++;45                 }46             }47         }48         cout << num << endl;49     }50     return 0;51 }

POJ 2386 Lake Counting

2、

　　题意：求从‘@’出发，每次只能从4个方向走，且只能走到‘.’的位置，求全部能走到的个数。

　　思路：从‘@’出发DFS一遍即可。

1 #include
      
        2 #include
       
         3 using namespace std; 4 void f(char **p,int x,int y,int x0,int y0,int &sum); 5 int main() 6 { 7     int x, y; 8     while (cin >> x >> y, x != 0 && y != 0) 9     {10         char **p = new char *[y];11         for (int i = 0; i < y; i++) *(p + i) = new char[x];12         int x0, y0;13         for (int i = 0; i < y; i++)14             for (int j = 0; j < x; j++)15             {16                 cin >> p[i][j];17                 if (p[i][j] == '@')18                 {19                     y0 = i;20                     x0 = j;21                 }22             }23         int sum=0;24         f(p, x0, y0, x, y, sum);25         cout << sum << endl;26         for (int i = 0; i < y; i++) delete[]p[i];27         delete[]p;28         p = NULL;29     }30     return 0;31 }32 void f(char **p, int x, int y, int x0, int y0, int &sum)33 {34     if (x >= x0 || x < 0 || y >= y0 || y < 0) return;35     if (p[y][x] == '#') return;36     else37     {38         sum++;39         p[y][x] = '#';40         f(p, x + 1, y, x0, y0, sum);41         f(p, x - 1, y, x0, y0, sum);42         f(p, x, y + 1, x0, y0, sum);43         f(p, x, y - 1, x0, y0, sum);44     }45 }

View Code

3、POJ 1321 棋盘问题

　　题意：在一个n*n的矩阵里放k个棋子，只能放在棋盘区域，同时保证每行每列只有最多只有一个棋子。求方案数

　　思路：DFS，按行开始放。

1 #include
      
        2 using namespace std; 3 int n, k; 4 char m[10][10]; 5 int cnt = 0; 6 bool Judge(int r, int c) 7 { 8     for (int i = 0; i < n; i++) 9     {
    //判断列是否只有一个10         if (i == r) continue;11         if (m[i][c] == '@') return false;12     }13     return true;14 }15 void DFS(int r, int num)16 {
    //按行放17     if (num == 0)18     {19         cnt++;20         return;21     }22     if (r == n)return;23     for (int i = 0; i < n; i++)24     {25         if (m[r][i] == '#')26         {27             if (Judge(r, i))28             {29                 m[r][i] = '@';30                 DFS(r + 1, num - 1);31                 m[r][i] = '#';32             }33         }34     }35     DFS(r + 1, num);//如果这一行不放棋子36 }37 int main()38 {39     while (~scanf("%d%d", &n, &k))40     {41         if (n == -1 && k == -1)break;42         for (int i = 0; i < n; i++)43         {44             for (int j = 0; j < n; j++) cin >> m[i][j];45         }46         cnt = 0;47         DFS(0, k);48         printf("%d\n", cnt);49     }50     return 0;51 }

View Code

4、POJ 2251 Dungeon Master(BFS)

　　题意：在一个三维空间里，询问能否从起点走到终点，若能，请求出最短时间。

　　思路：BFS，方向为6个。

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 char v[35][35][35];//[k][i][j]第k层第i行第j列 6 struct node 7 { 8     int k; 9     int r;10     int c;11     int steps;12     node(int kk = 0, int rr = 0, int cc = 0,int ss=0):k(kk),r(rr),c(cc),steps(ss){ }13 };14 node st, ed;15 int L, R, C;16 int dr[] = {
    1,-1,0,0,0,0};17 int dc[] = {
    0,0,1,-1,0,0};18 int dl[] = {
    0,0,0,0,1,-1};19 int main()20 {21     while (~scanf("%d%d%d",&L,&R,&C))22     {23         if (L == 0 && R == 0 && C == 0)break;24         for (int k = 0; k < L; k++)25         {26             for (int i = 0; i < R; i++)27             {28                 for (int j = 0; j < C; j++)29                 {30                     cin >> v[k][i][j];31                     if (v[k][i][j] == 'S') st.k = k, st.r = i, st.c = j,st.steps=0;32                     if (v[k][i][j] == 'E') ed.k = k, ed.r = i, ed.c = j;33                 }34             }35         }36         //BFS37         queue
         
          q;38         q.push(st);39         v[st.k][st.r][st.c] = '#';40         bool Find = false;41         while (!q.empty())42         {43             node cur = q.front();44             q.pop();45             if (cur.k == ed.k&&cur.r == ed.r&&cur.c == ed.c)46             {47                 ed.steps = cur.steps;48                 Find = true;49                 break;50             }51             int stp = cur.steps;52             for (int i = 0; i < 6; i++)53             {54                 int tr = cur.r + dr[i];55                 int tc = cur.c + dc[i];56                 int tl = cur.k + dl[i];57                 if (tr >= 0 && tr < R&&tc >= 0 && tc < C&&tl >= 0 && tl < L&&v[tl][tr][tc] != '#')58                 {59                     q.push(node(tl, tr, tc, stp + 1));60                     v[tl][tr][tc] = '#';61                 }62             }63         }64         if (Find) printf("Escaped in %d minute(s).\n", ed.steps);65         else printf("Trapped!\n");66     }67     return 0;68 }

View Code

5、HDU 2717/POJ 3278 Catch That Cow

　　题意：在一个数轴上，给出人和牛的位置，每次人可以从当前位置p走到p+1或p-1或2*p的位置，问能抓到牛的最少移动次数。

　　思路：BFS，每次选择合法的走法。

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 int n, k; 6 struct node 7 { 8     int pos; 9     int steps;10     node(int p=0,int stp=0):pos(p),steps(stp){ }11 };12 bool vis[200010];13 int main()14 {15     while (~scanf("%d%d", &n, &k))16     {17         //BFS();18         memset(vis, 0, sizeof(vis));19         queue
         
          q;20         q.push(node(n,0));21         vis[n] = true;22         int ans = 0;23         while (!q.empty())24         {25             node t = q.front();26             q.pop();27             int pos = t.pos, stps = t.steps;28             if (pos == k)29             {30                 ans = stps;31                 break;32             }33             if (pos < k)34             {35                 if(!vis[pos+1])q.push(node(pos + 1, stps + 1)), vis[pos + 1]=true;36                 if(!vis[pos*2])q.push(node(pos * 2, stps + 1)),vis[pos*2]=true;37                 if(pos-1>0&&!vis[pos-1])q.push(node(pos - 1, stps + 1)),vis[pos-1]=true;38             }39             else40             {41                 if(!vis[pos-1])q.push(node(pos - 1, stps + 1)),vis[pos-1]=true;42             }43         }44         printf("%d\n", ans);45     }46 47     return 0;48 }

View Code

6、POJ 3279 Fliptile

　　题意：给出一个M*N的矩阵，元素为1或0，每次能够选择一个点反转，同时将其上下左右的点都反转(如果点存在的话)，问能使最终矩阵只剩下0时且反转次数最少时的选择反转的点（用矩阵给出）

　　思路：如果第一行我们要反转的点已经确定，那么第一行的0和1的状态就确定，那么第二行的反转的点就会确定，因为此时只有反转第二行的点才能对第一行的1产生影响。走到最后一行，如果在反转最后一行后最后一行都为0，那么我们可以确定这是一种方案。我们枚举第一行选择反转的点的状态，就能知道最后满足题意的反转的方案。

1 //最多15位，用2进制状态压缩。枚举第一层的反转情况。第一层确定，后面反转状态的都会确定下来 2 #include
      
        3 using namespace std; 4 const int maxn = 16; 5 const int maxp = 16 * 16; 6 int init[maxn];//存初始状态 7 int flipstate[maxn];//存反转状态 8 int state[maxn];//存中间的状态 9 int ans[maxn],steps;//存结果10 int n, m;11 void DFS(int r, int cnt)12 {13     if (r == n)14     {15         if (state[n - 1] == 0)16         {17             if (cnt < steps)18             {19                 for (int i = 0; i < n; i++) ans[i] = flipstate[i];20                 steps = cnt;21             }//由于我们按照第一行反转状态从小到大DFS，所以如果相等，肯定前面已经保存的字典序小，所以不用再进行判断及赋值操作22         }23         return;24     }25     flipstate[r] = 0;26 27     for (int i = m-1; i>=0; --i)28     {
    //从左往右遍历29         if (state[r - 1] & (1 << i))//前一行为130         {31             flipstate[r] |= 1 << i;//该行灯反转32             state[r - 1] ^= (1 << i);//保存反转后对格子的影响33             state[r] ^= (1 << i);34             if (i + 1 <= m - 1) state[r] ^= (1 << (i + 1));35             if(i-1>=0) state[r] ^= (1 << (i - 1));36             if (r + 1 < n) state[r + 1] ^= (1 << i);37             cnt++;//反转次数累加38         }39     }40     DFS(r + 1, cnt);41 }42 void Solve()43 {44     int total = (1 << m) - 1;45     steps = maxp;46     for (int st = 0; st <= total; st++)47     {48         flipstate[0] = st;49         memcpy(state, init, sizeof(init));50         int cnt = 0;51         for (int i = m - 1; i >= 0; --i)52         {53             if (st&(1 << i))54             {55                 state[0] ^= (1 << i);56                 if (i + 1 <= m - 1)state[0] ^= (1 << (i + 1));57                 if (i - 1 >= 0) state[0] ^= (1 << (i - 1));58                 state[1] ^= (1 << i);59                 cnt++;60             }61         }62         DFS(1, cnt);63     }64 }65 int main()66 {67     while (~scanf("%d%d", &n, &m))68     {69         memset(init, 0, sizeof(init));70         for (int i = 0; i < n; i++)71         {72             for (int j = m - 1; j >= 0; --j)73             {74                 int num;75                 scanf("%d", &num);76                 if (num == 1) init[i] |= (1 << j);77             }78         }79         Solve();80         if (steps == maxp) printf("IMPOSSIBLE\n");81         else82         {83             for (int i = 0; i < n; i++)84             {85                 for (int j = m - 1; j >= 0; --j)86                 {87                     if (j < m - 1) printf(" ");88                     if (ans[i] & (1 << j))printf("1");89                     else printf("0");90                 }91                 printf("\n");92             }93         }94     }95     return 0;96 }

View Code

7、POJ 1426 Find The Multiple

　　题意：对于给定的数n,找到一个数是其倍数，同时该数中只含有1或0.

　　思路：DFS，从1开始枚举，若不是n的倍数，则*10或*10+1,当枚举的数位数超过19位后，直接舍弃。题目能够保证在long long的范围里有解。

1 //对于n，找到一个只包含数字1和0的数，使它为n的倍数 2 #include
      
        3 #include
       
         4 using namespace std; 5 long long ans,n; 6 bool flag = false; 7 void DFS(long long t,int k) 8 { 9     if (flag||k>19) return;10     if (t%n == 0)11     {12         flag = true;13         ans = t;14         return;15     }16     DFS(t * 10,k+1);17     if (flag) return;18     DFS(t * 10 + 1,k+1);19 }20 int main()21 {22     while(~scanf("%d",&n))23     {24         if (n == 0) break;25         flag = false;26         DFS(1,1);27         printf("%lld\n",ans);28     }29 30 31     return 0;32 }

View Code

8、POJ 3126 Prime Path(素数变换路径)

　　题意：给出一个4位素数，在给出一个要求的素数，问通过最少的变换次数(每次只能把当前素数的某一位换成其他数字，同时变换后的数字要求是素数)从初始的素数变换到要求的素数。

　　思路：先打表判断某一个数是否为素数；然后对于当前一个素数，对其所有位都进行模拟变换，注意最高位不能变换为0，BFS。

1 #include
      
        2 #include
       
         3 using namespace std; 4 const int maxn = 10005; 5 bool isp[maxn]; 6 int prime[maxn], cnt; 7 int ans; 8 void makePrime() 9 {10     memset(isp, true, sizeof(isp));11     isp[0] = isp[1] = false;12     cnt = 0;13     for (int i = 2; i < maxn; ++i)14     {15         if (isp[i])//是素数16         {17             prime[cnt++] = i;//保存该素数18         }19         for (int j = 0; j < cnt && i * prime[j] < maxn; ++j)20         {21             isp[i * prime[j]] = false;//当前的数乘以所有已算出的素数都不是素数22             if (i % prime[j] == 0)//如果i能被某一个最小的素数整除，则退出23             {24                 break;25             }26         }27     }28 }29 int a, b;30 int vis[maxn];31 32 void BFS()33 {34     queue
        
         q;35     q.push(a);36     vis[a] = 1;37     while (!q.empty())38     {39         int v = q.front();40         q.pop();41         //printf("%d %d\n", v, vis[v]);42         if (v == b)43         {44             ans = vis[v]-1;45             return;46         }47         int base1 = 10,base2=1;48         for (int i = 0; i < 4; i++)49         {50             for (int j = 0; j <= 9; j++)51             {52                 if (v%base1 / base2 == j)continue;53                 if (i == 3 && j == 0)continue;54                 int tmp = v / base1*base1 + v%base2 + j*base2;55                 if (isp[tmp]&&!vis[tmp])56                 {57                     vis[tmp] = vis[v]+1;58                     q.push(tmp);59                     60                 }61             }62             base1 *= 10;63             base2 *= 10;64         }65     }66     67 }68 int main()69 {70     makePrime();71     int t;72     scanf("%d", &t);73     while (t--)74     {75         scanf("%d%d", &a, &b);76         memset(vis, 0, sizeof(vis));77         BFS();78         printf("%d\n", ans);79     }80     return 0;81 }

View Code

9、POJ 3087 Shuffle'm Up

　　题意：初始有两堆扑克，问能否通过变换得到指定的一堆扑克，若能，求最少次数。

　　思路：BFS，如果变换后再拆分后的结果某次等于初始状态，说明无法变换到指定的堆。否则，不断进行模拟变换和拆分。

1 #include
      
        2 #include
       
         3 using namespace std; 4 char s1[105]; 5 char s2[105]; 6 char des[210]; 7 int main() 8 { 9     int t;10     int Case = 1;11     scanf("%d", &t);12     while (t--)13     {14         int c;15         scanf("%d", &c);16         scanf("%s", s1);17         scanf("%s", s2);18         scanf("%s", des);19         int cnt = 0;20         char t1[105], t2[105],ts[210];21         memcpy(t1, s1, sizeof(s1));22         memcpy(t2, s2, sizeof(s2));23         while (1)24         {25             int len = 0;26             for (int i = 0; i < c; i++)27             {28                 ts[len] = t2[i];29                 len++;30                 ts[len] = t1[i];31                 len++;32             }33             cnt++;34             ts[len] = '\0';35             if (strcmp(ts,des)==0)36             {37                 break;38             }39             for (int i = 0; i < c; i++) t1[i] = ts[i];40             for (int i = c; i < 2 * c; i++) t2[i-c] = ts[i];41             if (strcmp(t1,s1)==0 && strcmp(t2,s2)==0)42             {43                 cnt = -1;44                 break;45             }46         }47         printf("%d %d\n", Case, cnt);48         Case++;49     }50 51 52     return 0;53 }

View Code

10、poj 3414 Pots (bfs+路径记录)

　　题意：初始有两个空杯，每次可以选择装满一个杯子、倒空一个杯子、从一个杯子倒水到另一个杯子（直到倒水的杯子为空或被倒水的杯子已经被倒满），问能否使最后某个杯子中有C体积的水，能的话求出最少次数，并输出步骤顺序。

　　思路：BFS，用数组来模拟队列（因为需要保存步骤），同时记录杯子水的状态，没有出现过则加入“队列”。如果最后“队列”为“空”（当前指针和长度相等），则说明无法达到题目要求的状态。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 int A, B, C; 7 struct opt 8 { 9     int a;10     int b;11     char op;12     char from;13     char to;14     int pre;15     int cnt;16     opt(int aa=0,int bb=0,char opp='f',char fr='0',char too='1',int pr=0,int ct=0):a(aa),b(bb),op(opp),from(fr),to(too),pre(pr),cnt(ct){ }17 };18 bool vis[110][110];19 opt ed;20 opt q[1000005];21 void Print(int id)22 {23     if (id != 0)24     {25         Print(q[id].pre);26         switch (q[id].op)27         {28         case 'd':printf("DROP(%c)\n", q[id].from);29             break;30         case 'f':printf("FILL(%c)\n", q[id].from);31             break;32         case 'p':printf("POUR(%c,%c)\n", q[id].from, q[id].to);33         }34     }35 }36 int main()37 {38     while (~scanf("%d%d%d", &A, &B, &C))39     {40         memset(vis, 0, sizeof(vis));41         memset(q, 0, sizeof(q));42         vis[0][0] = true;43         int first = 0;44         int len = 1;45         bool flag = false;46         while (first
          
           =0?A:t.a+t.b), tb=(t.b-(A-t.a)>=0?t.b-(A-t.a):0);82                 if (!vis[ta][tb])q[len++] = opt(ta, tb, 'p', '2', '1', first - 1, t.cnt + 1), vis[ta][tb] = true;83                 ta = (t.a - (B - t.b) >= 0 ? t.a - (B - t.b) : 0), tb = (t.a - (B - t.b) >= 0 ? B : t.b + t.a);84                 if (!vis[ta][tb])q[len++] = opt(ta, tb, 'p', '1', '2', first - 1, t.cnt + 1), vis[ta][tb] = true;85             }86         }87         if (flag)88         {89             printf("%d\n", ed.cnt);90             Print(first - 1);91         }92         else printf("impossible\n");93     }94     return 0;95 }

View Code

11、UVA11624 Fire!

　　题意：有一个迷宫，有一个人，同时又若干处着火，问能否在火烧到自己之前逃出迷宫，即走到边界，能的话求最少的时间。

　　思路：首先对火进行BFS，初始将所有着火点都放入队列，求出火蔓延到每一处可达的地方的时间；然后对人进行BFS，若某一处可以到达、且没走过、且走到时的时间小于火势蔓延到该处的时间，则加入队列。

1 #include
      
         2 #include
       
          3 #include
        
           4 using namespace std;  5 const int INF = 0x7fffffff;  6 const int maxn = 1005;  7 int firetime[maxn][maxn];  8 char mp[maxn][maxn];  9 int xj, yj; 10 int n, m; 11 int dx[] = { 0,0,1,-1 }; 12 int dy[] = { 1,-1,0,0 }; 13 struct point 14 { 15     int r; 16     int c; 17     int t; 18     point(int rr=0,int cc=0,int tt=0):r(rr),c(cc),t(tt){ } 19 }; 20 bool vis[maxn][maxn]; 21 void BFSf() 22 { 23     queue
         
          q; 24     for (int i = 0; i < n; i++) 25     { 26         for (int j = 0; j < m; j++) 27         { 28             if (mp[i][j] == 'F') q.push(point(i, j, 0)),vis[i][j]=true; 29         } 30     } 31     while (!q.empty()) 32     { 33         point t = q.front(); 34         q.pop(); 35         firetime[t.r][t.c] = t.t; 36         for (int i = 0; i < 4; i++) 37         { 38             int dr = t.r + dx[i]; 39             int dc = t.c + dy[i]; 40             if (dr < n&&dr >= 0 && dc < m&&dc >= 0) 41             { 42                 if (mp[dr][dc] != '#'&&!vis[dr][dc]) 43                 { 44                     vis[dr][dc] = true; 45                     q.push(point(dr, dc, t.t + 1)); 46                 } 47             } 48         } 49     } 50 } 51 int ans = INF; 52  53 void BFSj() 54 { 55     queue
          
           q; 56     q.push(point(xj, yj, 0)); 57     vis[xj][yj] = true; 58     while (!q.empty()) 59     { 60         point t = q.front(); 61         q.pop(); 62         if (t.r == n - 1 || t.r == 0 || t.c == m - 1 || t.c == 0) 63         { 64             ans = t.t; 65             return; 66         } 67         for (int i = 0; i < 4; i++) 68         { 69             int dr = t.r + dx[i]; 70             int dc = t.c + dy[i]; 71             if (dr <= n - 1 && dr >= 0 && dc <= m - 1 && dc >= 0) 72             { 73                 if (mp[dr][dc] != '#' && !vis[dr][dc] && t.t + 1 < firetime[dr][dc]) 74                 { 75                     vis[dr][dc] = true; 76                     q.push(point(dr, dc, t.t + 1)); 77                 } 78             } 79         } 80     } 81     ans = INF; 82 } 83 int main() 84 { 85     //std::ios::sync_with_stdio(false); 86     int t; 87     scanf("%d", &t); 88     while (t--) 89     { 90         scanf("%d%d", &n, &m); 91         for (int i = 0; i < n; i++) 92         { 93             for (int j = 0; j < m; j++) 94             { 95                 cin >> mp[i][j]; 96                 if (mp[i][j] == 'J') xj = i, yj = j; 97                 firetime[i][j] = INF; 98             } 99         }100         memset(vis, 0, sizeof(vis));101         BFSf();102         memset(vis, 0, sizeof(vis));103         ans = INF;104         BFSj();105         if (ans == INF)106         {107             printf("IMPOSSIBLE\n");108         }109         else110         {111             printf("%d\n", ans+1);112         }113     }114     return 0;115 }

View Code

12、HDU1241 Oil Deposits

　　题意：给出一个地图，上面标记有油的地方，问有多少个油田（上下左右、左上左下右上右下如果和该处都有油，则属于同一个油田）

　　思路：简单DFS。

1 #include
      
        2 #include
       
         3 using namespace std; 4 char mp[110][110]; 5 int n, m; 6 bool vis[110][110]; 7 int dr[] = {
    0,-1,-1,-1,0,1,1,1}; 8 int dc[] = {-1,-1,0,1,1,1,0,-1}; 9 void DFS(int r, int c)10 {11     vis[r][c] = true;12     for (int i = 0; i < 8; i++)13     {14         int tr = r + dr[i];15         int tc = c + dc[i];16         if (tr < n&&tr >= 0 && tc < m&&tc >= 0)17         {18             if (mp[tr][tc] == '@' && !vis[tr][tc])19                 DFS(tr, tc);20         }21     }22 }23 int main()24 {25     while (~scanf("%d%d", &n, &m))26     {27         if (m == 0) break;28         for (int i = 0; i < n; i++)29         {30             for (int j = 0; j < m; j++) cin >> mp[i][j];31         }32         memset(vis, 0, sizeof(vis));33         int cnt = 0;34         for (int i = 0; i < n; i++)35         {36             for (int j = 0; j < m; j++)37             {38                 if (mp[i][j] == '@' && !vis[i][j])39                 {40                     DFS(i, j);41                     cnt++;42                 }43             }44         }45         printf("%d\n", cnt);46     }47 48     return 0;49 }

View Code

13、HDU 1495 非常可乐(广搜BFS)

　　题意：有一瓶满的可乐，还有两个杯子。每次可以从一个容器倒到另一个容器（直到一个为空或一个为满），问能否使该瓶可乐平分。

　　思路：BFS。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 int S, N, M; 7 struct node 8 { 9     int s;10     int n;11     int m;12     int step;13     node(int ss=0,int nn=0,int mm=0,int st=0):s(ss),n(nn),m(mm),step(st){ }14 };15 bool vis[110][110][110];16 int main()17 {18     while (~scanf("%d%d%d", &S, &N, &M))19     {20         if (S == 0 && N == 0 && M == 0) break;21         if (S % 2 == 1)22         {23             printf("NO\n");24             continue;25         }26         memset(vis, 0, sizeof(vis));27         queue
          
           q;28         q.push(node(S, 0, 0, 0));29         vis[S][0][0] = true;30         bool flag = false;31         int ans;32         while (!q.empty())33         {34             node t = q.front();35             q.pop();36             if ((t.s == S / 2 && t.n == S / 2) || (t.s == S / 2 && t.m == S / 2) || (t.n == S / 2 && t.m == S / 2))37             {38                 flag = true;39                 ans = t.step;40                 break;41             }42             if (t.s)43             {44                 int ts = (t.s - (N - t.n) >= 0 ? t.s - (N - t.n) : 0);45                 int tn = (t.s - (N - t.n) >= 0 ? N : t.s + t.n);46                 if (!vis[ts][tn][t.m]) q.push(node(ts, tn, t.m, t.step + 1)),vis[ts][tn][t.m]=true;47                 ts = (t.s - (M - t.m) >= 0 ? t.s - (M - t.m) : 0);48                 int tm = (t.s - (M - t.m) >= 0 ? M : t.s + t.m);49                 if (!vis[ts][t.n][tm]) q.push(node(ts, t.n, tm, t.step + 1)), vis[ts][t.n][tm] = true;50             }51             if (t.n)52             {53                 int tn = 0, ts = t.s + t.n;54                 if (!vis[ts][tn][t.m]) q.push(node(ts, tn, t.m, t.step + 1)), vis[ts][tn][t.m] = true;55                 tn = (t.n - (M - t.m) >= 0 ? t.n - (M - t.m) : 0);56                 int tm = (t.n - (M - t.m) >= 0 ? M : t.n + t.m);57                 if (!vis[t.s][tn][tm])q.push(node(t.s, tn, tm, t.step + 1)), vis[t.s][tn][tm] = true;58             }59             if (t.m)60             {61                 int tm = 0, ts = t.s + t.m;62                 if (!vis[ts][t.n][tm])q.push(node(ts, t.n, tm, t.step + 1)), vis[ts][t.n][tm] = true;63                 tm = (t.m - (N - t.n) >= 0 ? t.m - (N - t.n) : 0);64                 int tn = (t.m - (N - t.n) >= 0 ? N : t.m + t.n);65                 if (!vis[t.s][tn][tm])q.push(node(t.s, tn, tm, t.step + 1)), vis[t.s][tn][tm] = true;66             }67         }68         if (flag)printf("%d\n", ans);69         else printf("NO\n");70     }71 72 73     return 0;74 }

View Code

14、hdu 2612 Find a way (BFS)

　　题意：有两个人，有几家KFC店，现在这两个人商量到某一家KFC。求两个人到KFC店的最少的用时，每次走一步花费11分钟。

　　思路：对两个人分别BFS，求出其到各家KFC店的最短用时。

1 #include
      
        2 #include
        3 #include
        
          4 #include
         
           5 using namespace std; 6 char mp[210][210]; 7 map
          
           
            , int>kfc; 8 bool vis[210][210]; 9 const int maxt = 0x7fffffff;10 struct node11 {12 int r;13 int c;14 int tm;15 node(int rr=0,int cc=0,int tt=0):r(rr),c(cc),tm(tt){ }16 };17 int Yx, Yy, Mx, My;18 int n, m;19 int dx[] = { 0,0,1,-1 };20 int dy[] = { 1,-1,0,0 };21 int ans,cntkfc;22 void BFS(int inir,int inic)23 {24 memset(vis, 0, sizeof(vis));25 cntkfc = kfc.size();26 queue
            
             q;27 q.push(node(inir,inic, 0));28 vis[inir][inic] = true;29 pair
             
              p;30 while (!q.empty())31 {32 node t = q.front();33 p.first = t.r, p.second = t.c;34 q.pop();35 if (kfc[p])36 {37 cntkfc--;38 if (kfc[p] > 11) ans = min(ans, kfc[p] + t.tm - 11);39 kfc[p] += t.tm;40 if (cntkfc == 0)return;41 }42 for (int i = 0; i < 4; i++)43 {44 int tr = t.r + dx[i];45 int tc = t.c + dy[i];46 if (tr >= 0 && tr < n&&tc >= 0 && tc < m)47 {48 if (mp[tr][tc] != '#' && !vis[tr][tc])49 {50 vis[tr][tc] = true;51 q.push(node(tr, tc, t.tm + 11));52 }53 }54 }55 }56 }57 int main()58 {59 while (~scanf("%d%d", &n, &m))60 {61 kfc.clear();62 for (int i = 0; i < n; i++)63 {64 for (int j = 0; j < m; j++)65 {66 cin >> mp[i][j];67 if (mp[i][j] == 'Y') Yx = i, Yy = j;68 if (mp[i][j] == 'M')Mx = i, My = j;69 if (mp[i][j] == '@') kfc[make_pair(i, j)] = 11;70 }71 }72 ans = maxt;73 BFS(Yx, Yy);74 BFS(Mx, My);75 printf("%d\n", ans);76 }77 return 0;78 }

View Code

进阶题

1、Eight hdu 1043/POJ 1077（双向广搜+康拓展开）

　　题意：八数码，在一个九宫格里给出1~8的位置，剩下一个为空。求经过最少多少步后能够达到目标状态，并且给出走法（字符串）

　　思路：①双向广搜+康拓展开hash

　　　　　　1、由于每一种状态都是0~8的一个排列，每一个排列对应康拓展开的一个值，建立hash，以便判重

　　　　　　2、双向广搜，此处用两个队列同时进行，用vis分别记录在此队列中某一状态是否出现过。并用数组来记录所有的走法。当两者相遇时，则递归输出路径。

　　　　　　3、由于在八数码中，任意交换两个数字的位置不改变逆序数的奇偶性，所以可以事先判断初始和目标状态的逆序数的奇偶性。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 using namespace std;  7   8 const int maxn = 400000;  9 const char* DIR1 = "udlr";//上下左右 10 const char* DIR2 = "durl";//下上右左，因为从终点开始广搜，然后从中间状态要走到终点，方向反 11  12 int kthash[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320 }; //康拓展开的阶乘值 13  14 int x; //初始状态x的位置 15  16 int dir[] = { -3, 3, -1, 1 };//在数组里的位置变化。向上走位置-3，向下走位置+3，向左走位置-1，向右走位置+1 17  18 int vis1[maxn];//起点广搜标记 19 int vis2[maxn];//终点广搜标记 20  21 char ss[] = "123456780";//目标即最终状态 22 char str[10];//初始状态 23  24 struct Node 25 { 26     int x;//'x'的位置 27     char str[10];//棋子的状态 28 };//用于广搜时队列的元素 29  30 struct Step 31 { 32     int cnt; 33     char dir; 34 }pre[maxn];//记录路径 35 int Hush(char* a)  //计算康托展开值 36 { 37     int s = 0, i, j, k; 38     for (i = 0; i<9; i++) 39     { 40         k = 0; 41         for (j = 0; j
           
            a[i])k++; 43 s += k*kthash[i]; 44 } 45 return s; 46 } 47 48 49 void printfff(int x) //追溯到起点输出路径 50 { 51 if (pre[x].cnt == -1) return; 52 printfff(pre[x].cnt); 53 cout << pre[x].dir; 54 } 55 56 int judge(int x, int i) //判断是否越界，x为'0'(代表'x')在一维数组的位置 57 { 58 int xx = x / 3; //行 59 int yy = x % 3; //列 60 if (i == 3)//向右走 61 { 62 int yyy = yy + 1; 63 if (yyy > 2) return 0; 64 } 65 if (i == 2)//向左走 66 { 67 int yyy = yy - 1; 68 if (yyy < 0) return 0; 69 } 70 if (i == 1)//向下走 71 { 72 int xxx = xx + 1; 73 if (xxx>2) return 0; 74 } 75 if (i == 0)//向上走 76 { 77 int xxx = xx - 1; 78 if (xxx < 0) return 0; 79 } 80 return 1; 81 } 82 83 void bfs() 84 { 85 memset(vis1, 0, sizeof(vis1));//从起点BFS标记数组 86 memset(vis2, 0, sizeof(vis2));//从终点BFS标记数组 87 88 queue
            
              q1, q2;//q1起点BFS，q2终点BFS 89 Node p1, p2; 90 91 int count = 2; 92 strcpy(p1.str, str); //初始状态 93 p1.x = x; //初始x的位置 94 //cout << p1.str << endl; 95 strcpy(p2.str, ss); //最终状态 96 p2.x = 8; //最终x的位置 97 //cout << p2.str << endl; 98 q1.push(p1); 99 q2.push(p2);100 vis1[Hush(str)] = 1;//为0表示没有访问，否则表示pre[]访问位置101 vis2[Hush(ss)] = 2;102 pre[1].cnt = -1; //起点标记103 pre[2].cnt = -1; //终点标记104 while (!q1.empty() && !q2.empty())105 {106 Node u = q1.front();107 q1.pop();108 int p = Hush(u.str);109 if (vis2[p]) //在终点广搜中出现过110 {111 printfff(vis1[p]);//先打印从起点到该点112 int k = vis2[p];113 while (pre[k].cnt != -1)//打印从该点到终点114 {115 cout << pre[k].dir;116 k = pre[k].cnt;117 }118 cout << endl;119 return;120 }121 else //未找到目标状态122 {123 Node u2;124 for (int i = 0; i < 4; i++)125 {126 u2 = u;127 if (!judge(u.x, i)) continue;128 int xx = u.x + dir[i]; //x的新地址129 swap(u2.str[u.x], u2.str[xx]);130 u2.x = xx;131 int v = Hush(u2.str);132 if (vis1[v]) continue; //已访问133 vis1[v] = ++count;134 pre[count].dir = DIR1[i]; //记录方向135 pre[count].cnt = vis1[p];136 q1.push(u2);137 }138 }139 140 u = q2.front();141 q2.pop();142 p = Hush(u.str);143 if (vis1[p])144 {145 printfff(vis1[p]);146 int k = vis2[p];147 while (pre[k].cnt != -1)148 {149 cout << pre[k].dir;150 k = pre[k].cnt;151 }152 cout << endl;153 return;154 }155 else //未找到目标状态156 {157 Node u2;158 for (int i = 0; i < 4; i++)159 {160 u2 = u;161 if (!judge(u.x, i)) continue;162 int xx = u.x + dir[i]; //x的新地址163 swap(u2.str[u.x], u2.str[xx]);164 u2.x = xx;165 int v = Hush(u2.str);166 if (vis2[v]) continue; //已访问167 vis2[v] = ++count;168 pre[count].dir = DIR2[i]; //记录方向169 pre[count].cnt = vis2[p];170 q2.push(u2);171 }172 }173 }174 cout << "unsolvable" << endl;175 }176 177 178 int main()179 {180 181 char s[40];182 while (gets_s(s,40))183 {184 int k = 0;185 int t = 0;186 for (int i = 0; s[i] !='\0'; i++)187 {188 if (s[i] == ' ')continue;189 if (s[i] == 'x')190 {191 str[k] = '0'; 192 x = k;193 }194 else str[k] = s[i];195 k++;196 }197 str[k] = '\0';198 199 for (int i = 0; i<9; i++) //逆序数判断是否可行200 {201 if (str[i] == '0')continue;202 for (int j = 0; j
             
              str[i])t++;206 }207 }208 if (t & 1) cout << "unsolvable" << endl;//逆序数为奇数，则不可行209 else bfs();210 }211 return 0;212 }

View Code

2、Eight II HDU 3567

　　题意：和上题类似，不过不再是Special Judge,需要给出从初始状态到目标状态的最小移动步数，同时如果在最小步数下有多种走法，给出字典序最小的走法。

　　思路：①双向广搜+康拓展开hash

　　　　　　1、由于需要进行路径的比较，用4进制表示路径来保存。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
              9 #include 
              
                10 #include
               
                 11 using namespace std; 12 13 #define LL __int64 14 const int maxn = (int)4e5 + 10; 15 const int INF = (int)1e8; 16 int ha[9] = { 1,1,2,6,24,120,720,5040,40320 };//康拓哈希 17 int dir[4][2] = { { 1,0 },{ 0,-1 },{ 0,1 },{ -1,0 } };//下d 左l 右r 上u 18 char d[10] = { "dlru" }; 19 LL dd[2][4] = { { 0,1,2,3 },{ 3,2,1,0 } }; 20 int vis[2][maxn], t, Min_ans;//vis记录最短到底目标的时间 21 char ans[maxn], get[maxn]; 22 LL c[2][maxn];//c[i][j]表示i状态下，j哈希值时的最小路径 23 LL mm[30]; //mm[i]表示4^i 24 struct node 25 { 26 int f[3][3];//状态 27 int x, y;//'0'的位置 28 int g;//表示在格子BFS中的步数 29 int flag;//0表示前BFS，1表示后BFS 30 LL path;//4进制表示的路径 31 int hash_num;//hash值 32 }; 33 int get_hash(node e)//康托展开，压缩空间。 34 { 35 int a[9], i, j, k = 0, ans = 0; 36 for (i = 0; i<3; i++) 37 { 38 for (j = 0; j<3; j++) 39 a[k++] = e.f[i][j]; 40 } 41 for (i = 0; i<9; i++) 42 { 43 k = 0; 44 for (j = 0; j
                
                 a[i])k++; 46 ans += ha[i] * k; 47 } 48 return ans; 49 } 50 string get_str(LL c, int flag, int kk)//从数字转换成路径 51 { 52 int str[100]; 53 int i, k = 0; 54 for (i = 0; i
                 
                  = 0; i--) 61 s += d[str[i]]; 62 return s; 63 } 64 void bfs(node e, node ee)//双向bfs 65 { 66 memset(vis, -1, sizeof(vis)); 67 int i, j, k, xx, yy, dis[2]; 68 dis[0] = dis[1] = 0; 69 node a, b; 70 e.hash_num = get_hash(e); 71 e.g = 0, e.flag = 0; 72 e.path = 0; 73 ee.hash_num = get_hash(ee); 74 ee.g = 0, ee.flag = 1; 75 ee.path = 0; 76 vis[0][e.hash_num] = 0; 77 vis[1][ee.hash_num] = 0; 78 if (e.hash_num == ee.hash_num) 79 { 80 printf("0\n\n"); return; 81 } 82 83 queue
                  
                   q; 84 q.push(e);//压入起点 85 q.push(ee);//压入终点 86 Min_ans = INF; 87 LL str; 88 string res; 89 while (!q.empty()) 90 { 91 e = q.front(); 92 q.pop(); 93 94 for (i = 0; i<4; i++) 95 { //四个方向 96 a = e; 97 a.x = e.x + dir[i][0]; 98 a.y = e.y + dir[i][1]; 99 if (a.x<0 || a.y<0 || a.x >= 3 || a.y >= 3)continue;100 swap(a.f[e.x][e.y], a.f[a.x][a.y]);101 k = get_hash(a);102 if (vis[e.flag][k] != -1)//如果已经访问过103 {104 if (e.g + 1>vis[e.flag][k])continue;105 else//如果可以更早到达106 {107 if (e.flag)str = dd[e.flag][i] * mm[e.g] + e.path;//后DFS108 else str = e.path * 4 + dd[e.flag][i];//前DFS109 if (c[e.flag][k]>str)110 c[e.flag][k] = str;111 }112 }113 else//没有访问过114 {115 vis[e.flag][k] = e.g + 1;116 if (e.flag)c[e.flag][k] = dd[e.flag][i] * mm[e.g] + e.path;117 else c[e.flag][k] = e.path * 4 + dd[e.flag][i];118 }119 a.hash_num = k;120 a.g++;121 a.path = c[e.flag][k];122 if (vis[e.flag ^ 1][k] != -1)//如果在另一个BFS中出现过123 {124 //cout<
                   
                    <
                    
                     Min_ans)130 { //如果大于131 cout << Min_ans << endl;132 cout << res << endl;133 return;134 }135 if (t
                     
                      0)res = s;143 }144 }145 q.push(a);146 }147 }148 }149 void init()150 { //4进制表示路径151 int i, j, k;152 mm[0] = 1;153 for (i = 1; i <= 30; i++)154 mm[i] = mm[i - 1] * 4;155 }156 int main()157 {158 init();159 char a[30], b[30];160 int T, tt = 0;161 scanf("%d", &T);162 while (T--)163 {164 int i, j, k, n;165 node e, pp;166 scanf("%s", a);167 scanf("%s", b);168 n = strlen(a);169 for (i = 0; i

View Code

3、HDU2181 哈密顿绕行世界问题(DFS)

　　题意：共有20各城市，给出每个城市相邻的3个城市，求从一个城市m出发，经过所有城市后回到m的所有方案，按字典序输出。

　　思路：每次判断是否走过，从小的城市开始DFS。

1 #include
      
        2 #include
       
         3 using namespace std; 4 int mp[25][3]; 5 int line[25]; 6 int vis[25]; 7 int Case; 8 void DFS(int st,int cur, int len) 9 {10     if (cur == st&&len == 21)11     {12         printf("%d: ", Case);13         for (int i = 0; i < 21; i++) printf(" %d", line[i]);14         printf("\n");15         Case++;16         return;17     }18     for (int i = 0; i < 3; i++)19     {20         if (!vis[mp[cur][i]]&&(mp[cur][i]!=st||len==20))21         {22             line[len] = mp[cur][i];23             vis[mp[cur][i]] = true;24             DFS(st, mp[cur][i], len + 1);25             vis[mp[cur][i]] = false;26         }27     }28 }29 int main()30 {31     int lct[3];32     for (int i = 1; i <= 20; i++)33     {34         for (int j = 0; j < 3; j++) scanf("%d", &mp[i][j]);35     }36     int m;37     memset(vis, 0, sizeof(vis));38     while (~scanf("%d", &m))39     {40         if (m == 0)break;41         Case = 1;42         line[0] = m;43         DFS(m,m, 1);44     }45     return 0;46 }

View Code

4、HDU3533 Escape(BFS)

　　题意：从（0,0）走到(n,m),图中有若干个炮塔，会周期性的对其朝向位置发射一颗子弹，子弹遇到边界或另一个炮塔就会消失。现在需要在给定时间内到达且不能被炮塔打到，每走一步或待在原地时间+1.

　　思路：先预处理在给定的时间内，每个炮塔发出的子弹在何时会到达何处。然后进行BFS。

1 #include
      
         2 #include
       
          3 #include
        
           4 using namespace std;  5 int m, n, k, d;//行数，列数，炮塔数，总能量  6 const int maxn = 105;  7 const int maxt = 1005;  8 bool iscan[maxn][maxn][maxt];//第i行第j列第dt时间能不能通过  9 bool vis[maxn][maxn][maxt];//第i行第j列第dt时间是否曾经走过 10 struct node 11 { 12     int r; 13     int c; 14     int t; 15     node(int rr=0,int cc=0,int tt=0):r(rr),c(cc),t(tt){ } 16 }; 17  18 bool ppos[maxn][maxn];//第i行第j列是否有炮塔 19  20 int dr[] = { 0,0,0,-1,1 }; 21 int dc[] = { 0,1,-1,0,0 }; 22 struct pao 23 { 24     int r; 25     int c; 26     int v;//子弹速度 27     int period;//周期 28     char dir;//朝向'N'上'S'下'W'左'E'右 29 }Pao[maxn]; 30 void Init()//初始化iscan数组 31 { 32     memset(vis, 0, sizeof(vis)); 33     memset(iscan, true, sizeof(iscan)); 34     memset(ppos, 0, sizeof(ppos)); 35     pao temp; 36     char op[3]; 37     for (int i = 0; i < k; i++) 38     { 39         scanf("%s%d%d%d%d", &op, &temp.period, &temp.v, &temp.r, &temp.c); 40         temp.dir = op[0]; 41         ppos[temp.r][temp.c] = true; 42         Pao[i] = temp; 43     } 44     memset(iscan[0][0], false, sizeof(iscan[0][0]));//敌人大本营肯定不能待 45     for (int i = 0; i < k; i++) 46     {
    //分别对每个炮塔进行初始化 47         pao p = Pao[i]; 48         memset(iscan[p.r][p.c], false , sizeof(iscan[p.r][p.c])); 49         bool flag = false; 50         //先判断在朝向上有无炮塔 51         int edr = 0, edc=0; 52         switch (p.dir)//找到子弹能够射的距离 53         { 54         case 'N': 55             edc = p.c; 56             for (edr = p.r - 1; edr >= 0; edr--) if (ppos[edr][edc])break; 57             if (edr < 0)edr = 0; 58             for (int ps = p.r - p.v,init=1; ps >= edr;init++, ps -= p.v) 59             {
    //枚举位置 60                 for (int t = init; t <= d; t += p.period) iscan[ps][p.c][t] = false; 61             } 62             break; 63         case 'S': 64             edc = p.c; 65             for (edr = p.r + 1; edr <= m; edr++)if (ppos[edr][edc])break; 66             if (edr > m) edr = m; 67             for (int ps = p.r + p.v, init = 1; ps <= edr; init++, ps += p.v) 68             {
    //枚举位置 69                 for (int t = init; t <= d; t += p.period) iscan[ps][p.c][t] = false; 70             } 71             break; 72         case 'W': 73             edr = p.r; 74             for (edc = p.c - 1; edc >= 0; edc--)if (ppos[edr][edc])break; 75             if (edc < 0)edc = 0; 76             for (int ps = p.c-p.v, init = 1; ps >= edc; init++, ps -= p.v) 77             {
    //枚举位置 78                 for (int t = init; t <= d; t += p.period) iscan[p.r][ps][t] = false; 79             } 80             break; 81         case 'E': 82             edr = p.r; 83             for (edc = p.c + 1; edc <=n; edc++)if (ppos[edr][edc])break; 84             if (edc > n)edc = n; 85             for (int ps = p.r + p.v, init = 1; ps <= edr; init++, ps += p.v) 86             {
    //枚举位置 87                 for (int t = init; t <= d; t += p.period) iscan[p.r][ps][t] = false; 88             } 89             break; 90         }    91     } 92 } 93 void BFS() 94 { 95     queue
         
          q; 96     q.push(node(0, 0,0)); 97     vis[0][0][0] = true; 98     while (!q.empty()) 99     {100         node u = q.front();101         q.pop();102         if (u.r == m&&u.c == n)103         {104             printf("%d\n", u.t);105             return;106         }107         for (int i = 0; i < 5; i++)108         {109             int tr = u.r + dr[i];110             int tc = u.c + dc[i];111             int tt = u.t + 1;112             if (tr <= m&&tr >= 0 && tc <= n&&tc >= 0)113             {
    //没有超范围114                 if (!ppos[tr][tc]&&!vis[tr][tc][tt] && iscan[tr][tc][tt]&&tt<=d)115                 {
    //没有访问过且能够走116                     q.push(node(tr, tc, tt));117                     vis[tr][tc][tt] = true;118                 }119             }120         }121     }122     printf("Bad luck!\n");123 }124 int main()125 {126     while (~scanf("%d%d%d%d", &m, &n, &k, &d))127     {128         Init();129         BFS();130     }131     return 0;132 }

View Code

5、DNA sequence HDU 1560

　　题意：给出若干个长度不一定相同的DNA序列，现在需要构造一个最短的序列，使每一个给出的DNA序列都是它的一个子序列（不一定连续）

　　思路：迭代深搜，对于某一个限制的长度，看看能否达到要求。对于某一个位置，看看能否放置某一个字母（如果所有序列剩下的需要匹配的第一个字符有它），有就进行一次DFS。

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5  6 char str[10][10];//记录n个字符串 7 int n, ans, deep, Size[10]; 8 char DNA[4] = { 'A','C','G','T' };//一共四种可能 9 10 void dfs(int cnt, int *len)11 {12     if (cnt > deep)//大于限制的深度，不用往下搜索13         return;14     int maxx = 0;//预计还要匹配的字符串的最大长度15     for (int i = 0; i
         
          maxx)19             maxx = t;20     }21     if (maxx == 0)//条件全部满足即为最优解22     {23         ans = cnt;24         return;25     }26     if (cnt + maxx > deep)//剪枝27         return;28     for (int i = 0; i<4; i++)29     {30         int pos[10];//保存在当前字符被选择为构造的字符串的字符时，剩下的字符串开始需要匹配的位置31         int flag = 0;//判断是否有字符串的当前要匹配的位置是该字符32         for (int j = 0; j
          
           > t;53     while (t--)54     {55         cin >> n;56         int minn = 0;57         for (int i = 0; i
           
            > str[i];60 Size[i] = strlen(str[i]);//记录长度61 if (Size[i]>minn)62 minn = Size[i];63 }64 ans = -1;65 deep = minn;//从最短长度开始搜索66 int pos[10] = { 0 };//记录n个字符串目前匹配到的位置67 while (1)68 {69 dfs(0, pos);70 if (ans != -1)71 break;72 deep++;//加深迭代73 }74 cout << ans << endl;75 }76 return 0;77 }

View Code

6、ZOJ 2477 Magic Cube 三阶魔方还原(IDA)

　　题意：给出一个打乱的魔方，需要把它还原。

　　思路：

　　　　1、用数组先预先给出12种旋转（6个面，顺逆时针）转的位置编号。

　　　　2、由于题目限制最多5次，对旋转次数进行迭代深搜，如果5次内无法解决，则输出-1.

1 #include
      
         2 #include
       
          3 using namespace std;  4 int T, deep;  5 char s[60];  6 int cent[7] = { 5,23,26,29,32,50 };//第4、0、1、2、3、5面每面中心的编号  7 int ex[7][9] = { { 1,2,3,4,6,7,8,9 },//第4、0、1、2、3、5面每面除去中心其他的编号  8 { 10,11,12,22,24,34,35,36 },  9 { 13,14,15,25,27,37,38,39 }, 10 { 16,17,18,28,30,40,41,42 }, 11 { 19,20,21,31,33,43,44,45 }, 12 { 46,47,48,49,51,52,53,54 } 13 }; 14  15 int get_h() 16 { 17     int res = 0; 18     for (int i = 0; i<6; i++) 19     { 20         int c = 0;//该面中和中心颜色不同的数目 21         for (int j = 0; j<8; j++) 22         { 23             if (s[ex[i][j]] != s[cent[i]])     c++; 24         } 25         res += c; 26     } 27     return res; 28 } 29 int wh[10], dd[10]; 30 /*//数组保存位置 31           1  2  3 32           4  5  6(第4面) 33           7  8  9 34 10 11 12 13 14 15 16 17 18 19 20 21 35 22 23 24 25 26 27 28 29 30 31 32 33 36 34 35 36 37 38 39 40 41 42 43 44 45 37 （第0面）46 47 48（第2面）  （第3面） 38          49 50 51（第5面） 39          52 53 54 40 */ 41 int ope[12][20] = {
    //用预处理的数组来代替每一种旋转，节约时间。共6个面，每个面顺逆时针，共12种 42     { 1,4,7,13,25,37,46,49,52,21,33,45,10,11,12,24,36,35,34,22 },//第0面逆时针-- 43     { 45,33,21,1,4,7,13,25,37,52,49,46,34,22,10,11,12,24,36,35 },//          <-|  //两者相互为旋转后的坐标 44     { 7,8,9,16,28,40,48,47,46,36,24,12,13,14,15,27,39,38,37,25 },//第1面逆时针 45     { 36,24,12,7,8,9,16,28,40,48,47,46,37,25,13,14,15,27,39,38 }, 46     { 9,6,3,19,31,43,54,51,48,39,27,15,16,17,18,30,42,41,40,28 },//第2面逆时针 47     { 39,27,15,9,6,3,19,31,43,54,51,48,40,28,16,17,18,30,42,41 }, 48     { 42,30,18,3,2,1,10,22,34,52,53,54,19,20,21,33,45,44,43,31 },//第3面逆时针 49     { 52,53,54,42,30,18,3,2,1,10,22,34,43,31,19,20,21,33,45,44 }, 50     { 15,14,13,12,11,10,21,20,19,18,17,16,1,2,3,6,9,8,7,4 },//第4面逆时针 51     { 18,17,16,15,14,13,12,11,10,21,20,19,7,4,1,2,3,6,9,8 }, 52     { 37,38,39,40,41,42,43,44,45,34,35,36,46,47,48,51,54,53,52,49 },//第5面逆时针 53     { 34,35,36,37,38,39,40,41,42,43,44,45,52,49,46,47,48,51,54,53 } 54 }; 55  56 bool dfs(int d) 57 { 58     char maze[60]; 59     int h = get_h(); 60     if (d + (h + 11) / 12 > deep)  return false; 61     if (h == 0 && d == deep)  return true; 62     for (int i = 0; i<12; i++) 63     { 64         memcpy(maze, s, sizeof(s)); 65         for (int j = 0; j<20; j++) 66         { 67             s[ope[i][j]] = maze[ope[i ^ 1][j]]; 68         } 69         wh[d] = i / 2; 70         if ((i & 1) == 0)   dd[d] = 1;//奇数为顺时针旋转 71         else    dd[d] = -1;//偶数为逆时针旋转 72         if (dfs(d + 1))    return true; 73         memcpy(s, maze, sizeof(maze)); 74     } 75 } 76  77 void scan(char &c) 78 { 79     char cc; 80     while (cc = getchar(), cc<'a' || cc>'z'); 81     c = cc; 82 } 83  84 int main() 85 { 86     //freopen("1in","r",stdin) ; 87     //freopen("1out","w",stdout); 88     scanf("%d", &T); 89     while (T--) 90     { 91         for (int i = 1; i <= 54; i++) 92         { 93             scan(s[i]); 94         }//以第4、0、1、2、3、5面保存 95         if (get_h() == 0)//不同数目为0 96         { 97             printf("0\n"); continue; 98         } 99         deep = 1;100         while (deep <= 5)//迭代深搜101         {102             if (dfs(0))  break;103             deep++;104         }105         if (deep > 5)106         {107             printf("-1\n");108         }109         else110         {111             printf("%d\n", deep);112             for (int i = 0; i

View Code

7、hdu 1072 nightmare

　　题意：有个身上绑着炸弹的人，要在迷宫中找到出口。每走一步到相邻位置炸弹倒计时-1，迷宫有若干处有可以重新设置炸弹倒计时的工具，走到那便能重新reset时间，工具被用后就会消失。但是，如果恰好炸弹倒计时为0时，他走到放有工具的地方或者走到出口，则还是会失败。如果能够成功，输出最小的移动步数。

　　思路：BFS。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 int n, m; 7 const int maxn = 10; 8 int mp[maxn][maxn]; 9 int stx, sty, edx, edy;10 struct node11 {12     int r;13     int c;14     int t;15     int cnt;16     node(int rr=0,int cc=0,int tt=0,int ct=0):r(rr),c(cc),t(tt),cnt(ct){ }17 };18 int ans;19 int dr[] = { 0,0,1,-1 };20 int dc[] = { 1,-1,0,0 };21 void BFS()22 {23     queue
          
           q;24     q.push(node(stx, sty, 6));25     while (!q.empty())26     {27         node u = q.front();28         q.pop();29         if (u.r == edx&&u.c == edy&&u.t > 0)30         {31             ans = u.cnt;32             return;33         }34         if (mp[u.r][u.c] == 4 && u.t > 0) u.t = 6,mp[u.r][u.c]=1;35         if (u.t == 0)continue;36         for (int i = 0; i < 4; i++)37         {38             int tr = u.r + dr[i];39             int tc = u.c + dc[i];40             if (tr < n&&tr >= 0 && tc < m&&tc >= 0)41             {42                 if (mp[tr][tc] != 0)43                 {44                     q.push(node(tr, tc, u.t - 1, u.cnt + 1));45                 }46             }47         }48     }49 }50 int main()51 {52     int T;53     scanf("%d", &T);54     while (T--)55     {56         scanf("%d%d", &n, &m);57         for (int i = 0; i < n; i++)58         {59             for (int j = 0; j < m; j++)60             {61                 scanf("%d", &mp[i][j]);62                 if (mp[i][j] == 2) stx = i, sty = j;63                 if (mp[i][j] == 3) edx = i, edy = j;64             }65         }66         ans = -1;67         BFS();68         printf("%d\n", ans);69     }70     return 0;71 }

View Code

8、HDU 3085 Nightmare Ⅱ (双向BFS)

　　题意：有个迷宫，有两只鬼，每秒可以在周围两步内布满分身，分身也能继续制造分身，直到把迷宫装满（忽略墙）。男孩每秒可以走3步，女孩每秒可以走1步。问男孩能否找到女孩，能则输出最小的时间。

　　思路：男孩和女孩进行双向BFS，同一轮，男孩走3步，女孩走1步，判断是否会被鬼抓到只需判断和两只鬼之间的水平和垂直距离。

1 //#include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 using namespace std;  6 const int maxn = 880;  7 int n, m;  8 int dir[4][2] = { 1,0,-1,0,0,1,0,-1 };  9 char maps[maxn][maxn]; 10 struct node 11 { 12     int x, y; 13 } now, Next, b, g, z[2]; 14 queue 
          
            q[2], qt;//q[0]为boy，q[1]为girl，qt为当前操作的队列 15 int step = 0; 16 void pre_maps() 17 { 18     //多组输入，清零 19     while (!q[0].empty()) 20         q[0].pop(); 21     while (!q[1].empty()) 22         q[1].pop(); 23     while (!qt.empty()) 24         qt.pop(); 25  26     int k = 0; 27     for (int i = 0; i
           
            = n || a.y >= m)//超出地图直接返回 54 return true; 55 for (int i = 0; i<2; i++) 56 { 57 if (maps[a.x][a.y] == 'X' || (abs(a.x - z[i].x) + abs(a.y - z[i].y)) <= 2 * step)//是墙，或者被鬼抓到返回 58 return true; 59 } 60 return false; 61 } 62 bool bfs(int k, int num, char start, char End) 63 { 64 qt = q[k];//用来表示当前层的搜索，队列也可以直接赋值 65 for (int i = 0; i

View Code

9、hdu1067-Gap(bfs+哈希)

　　题意：给出初始局面，先把11、21、31、41放在第1、2、3、4行的首位（和0交换），之后每次可以把0左边的数字的大1的数字和0交换（如果0左边为0，则该0不能交换）。问能否到达目标状态，可以的话求出最少最小移动步数。

　　思路：BFS，问题在与如何判重。此处用2^i来构建hash。

1 #include
      
         2 #include
       
          3 #include
        
           4 using namespace std;  5 int st[4][8];  6 long long qz[32];  7 int des[4][8] =   8 {  9     {
    11,12,13,14,15,16,17,0}, 10     {
    21,22,23,24,25,26,27,0}, 11     {
    31,32,33,34,35,36,37,0}, 12     {
    41,42,43,44,45,46,47,0} 13 }; 14 int pos[4][2]; 15 set
         
          vis; 16 int ans; 17  18 void Pre() 19 { 20     qz[0] = 1; 21     for (int i = 1; i < 32; i++) qz[i] = qz[i - 1] * 2; 22 } 23  24 long long Hush(int (*s)[8]) 25 { 26     long long ans = 0; 27     for (int i = 0; i < 4; i++) 28     { 29         for (int j = 0; j < 8; j++) ans +=1ll*qz[i * 8 + j] * s[i][j]; 30     } 31     return ans; 32 } 33  34 struct node 35 { 36     int p[4][2];//存0的位置 37     int s[4][8];//存状态 38     int step;//存步数 39 }; 40 int BFS() 41 { 42     queue
          
           q; 43     node start; 44     memcpy(start.p, pos, sizeof(pos)); 45     memcpy(start.s, st, sizeof(st)); 46     start.step = 0; 47     q.push(start); 48     long long v = Hush(st); 49     vis.insert(v); 50     while (!q.empty()) 51     { 52         node u = q.front(); 53         q.pop(); 54         if (memcmp(u.s, des, sizeof(des)) == 0) 55         { 56             return u.step; 57         } 58         int tp[4][2]; 59         int ts[4][8]; 60         for (int i = 0; i < 4; i++) 61         { 62             memcpy(tp, u.p, sizeof(tp)); 63             memcpy(ts, u.s, sizeof(ts)); 64             int r = tp[i][0]; 65             int c = tp[i][1]; 66             int lv = ts[r][c - 1]; 67             if (lv % 10 == 7||lv==0)continue; 68             int desr, desc; 69             int flag = true; 70             for (int i = 0; flag&&i < 4; i++) 71             { 72                 for (int j = 0; j < 8; j++) 73                 { 74                     if (ts[i][j] == lv + 1) 75                     { 76                         desr = i; 77                         desc = j; 78                         flag = false; 79                     } 80                 } 81             } 82             if (flag)continue; 83             ts[r][c] = lv + 1; 84             ts[desr][desc] = 0; 85             tp[i][0] = desr; 86             tp[i][1] = desc; 87             long long tv = Hush(ts); 88             if (!vis.count(tv)) 89             { 90                 vis.insert(tv); 91                 node t; 92                 memcpy(t.p, tp, sizeof(tp)); 93                 memcpy(t.s, ts, sizeof(ts)); 94                 t.step = u.step + 1; 95                 q.push(t); 96             } 97         } 98     } 99     return -1;100 }101 void Run()102 {103     vis.clear();104     int cnt = 0;105     for (int i = 0; i < 4; i++)106     {107         for (int j = 1; j < 8; j++)108         {109             scanf("%d", &st[i][j]);110             if (st[i][j] % 10 == 1)111             {112                 st[st[i][j] / 10-1][0] = st[i][j];113                 st[i][j] = 0;114                 pos[cnt][0] = i;115                 pos[cnt][1] = j;116                 cnt++;117             }118         }119     }120     if (memcmp(st, des, sizeof(des))==0) printf("0\n");121     else printf("%d\n", BFS());122 }123 int main()124 {125     Pre();126     int t;127     scanf("%d", &t);128     while (t--)129     {130         Run();131     }132     return 0;133 }

View Code

10、HDU 2102 A计划

　　题意：有个两层的迷宫，骑士需要在T时间内找到公主。传送器可以传到另一层的相同x,y位置，但如果有墙的话会被撞死，如果相同位置都有传送器的话会一直死循环。询问能否找到。

　　思路：BFS，对传送器特判。

1 #include
      
        2 #include
       
         3 using namespace std; 4 char mz[2][15][15]; 5 bool vis[2][15][15]; 6 int n, m, T; 7 int edz, edx, edy; 8 struct node 9 {10     int z;11     int x;12     int y;13     int t;14     node(int zz = 0,int xx=0,int yy=0,int tt=0):z(zz),x(xx),y(yy),t(tt){ }15 };16 int dr[] = { 1,-1,0,0 };17 int dc[] = {
    0, 0, 1, -1};18 bool BFS()19 {20     memset(vis, 0, sizeof(vis));21     queue
        
         q;22     q.push(node(0, 0, 0, 0));23     vis[0][0][0] = true;24     while (!q.empty())25     {26         node u = q.front();27         q.pop();28         if (u.z == edz&&u.x == edx&&u.y == edy&&u.t <= T)29         {30             return true;31         }32         if (u.t > T) return false;33         for (int i = 0; i < 4; i++)34         {35             int tr = u.x + dr[i];36             int tc = u.y + dc[i];37             if (tr < n&&tr >= 0 && tc < m&&tc >= 0 && mz[u.z][tr][tc] != '*' && !vis[u.z][tr][tc])38             {39                 if (mz[u.z][tr][tc] != '#')40                 {41                     vis[u.z][tr][tc] = true;42                     q.push(node(u.z, tr, tc, u.t + 1));43                 }44                 else45                 {46                     vis[!u.z][tr][tc] = vis[u.z][tr][tc] = true;47                     if (mz[!u.z][tr][tc] != '*'&&mz[!u.z][tr][tc] != '#')48                     {49                         q.push(node(!u.z, tr, tc, u.t + 1));50                     }51                 }52             }53         }54 55     }56     return false;57 }58 int main()59 {60     int C;61     scanf("%d", &C);62     while (C--)63     {64         scanf("%d%d%d", &n, &m,&T);65         for (int i = 0; i < 2; i++)66         {67             for (int j = 0; j < n; j++)68             {69                 for (int k = 0; k < m; k++)70                 {71                     cin >> mz[i][j][k];72                     if (mz[i][j][k] == 'P')73                     {74                         edz = i;75                         edx = j;76                         edy = k;77                     }78                 }79             }80         }81         if (BFS()) printf("YES\n");82         else printf("NO\n");83     }84     return 0;85 }

View Code

11、J - Travelling hdu 3001 BFS+状压

　　题意：求走遍所有城市的最小花费。每座城市最多经过两次。

　　思路：BFS。3进制来表示某座城市经过几次。

1 //bfs + 状态压缩：开始时把每一个点都入队，模拟3进制处理每个状态，最后 + 优化。  2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
             7 #include
           
             8 #include
            
              9 using namespace std; 10 #define N 12//最多12个城市 11 #define LL long long 12 const int inf = 0x3fffffff;//最大值 13 int g[N][N]; 14 int n, m, ans; 15 int mark[N][60000];//3^10=59064 j状态下走到i的时间 16 struct node 17 { 18 int x, t, s, cnt; //位置、时间、状态、个数 19 friend bool operator<(node a, node b) 20 { 21 return a.t>b.t; 22 } 23 }; 24 int gettmp(int x, int k) //得到X在3进制下的第K位是多少 25 { //判断该点是否经过了，经过了几次 26 int t; 27 while (x) 28 { 29 t = x % 3; 30 k--; 31 if (k == 0) 32 break; 33 x /= 3; 34 } 35 return k ? 0 : t; 36 } 37 void inti()//初始化数组 38 { 39 int i, j; 40 for (i = 1; i <= n; i++) 41 { 42 for (j = 0; j<(int)pow(3, n); j++) 43 mark[i][j] = inf; 44 } 45 } 46 void bfs() 47 { 48 int i; 49 priority_queue
             
              q;//时间小的优先级高 50 node cur, next; 51 for (i = 1; i <= n; i++) 52 { //一开始把每个点都加入队列 53 cur.x = i; 54 cur.s = pow(3, (i - 1));//状态，表示只有该点走过 55 cur.t = 0; 56 cur.cnt = 1;//经过城市一个 57 q.push(cur); 58 mark[i][0] = 0; 59 } 60 while (!q.empty()) 61 { 62 cur = q.top(); 63 q.pop(); 64 for (i = 1; i <= n; i++) 65 { 66 if (g[cur.x][i] == inf) //此路不通 67 continue; 68 next.cnt = cur.cnt; 69 next.s = cur.s; 70 next.t = cur.t + g[cur.x][i]; 71 if (ans
              
               = 2) //经过2次后就不能走了 76 continue; 77 next.s += pow(3, (i - 1)); //该点经过次数加一 78 if (t == 0) //经过一个新景点 79 { 80 next.cnt++; 81 if (next.cnt == n) 82 { 83 ans = min(ans, next.t); 84 continue; 85 } 86 } 87 if (next.t