1. 题目列表

• POJ3126（BFS）
• POJ3087（BFS）
• POJ3414（BFS+路径打印）

2. 广搜问题思路

BFS可以解决一般的搜索问题。对于搜索问题我们要明确以下四个关键要素：

• 初始状态
• 目标状态
• 状态转移的操作
• 节点合法性、剪枝的判断

此外，相较于DFS，BFS是以广度为第一条件搜索，即搜索路径长度为第一条件，因此，BFS搜索到的第一个可行解一般是问题的最优解。

3. POJ3126——Prime Path

3.1 题目描述

Description

The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices.
— It is a matter of security to change such things every now and then, to keep the enemy in the dark.
— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know!
— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door.
— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime!
— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds.
— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime.

Now, the minister of finance, who had been eavesdropping, intervened.
— No unnecessary expenditure, please! I happen to know that the price of a digit is one pound.
— Hmm, in that case I need a computer program to minimize the cost. You don't know some very cheap software gurus, do you?
— In fact, I do. You see, there is this programming contest going on... Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above.

1033
1733
3733
3739
3779
8779
8179

The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.

Input

One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros).

Output

One line for each case, either with a number stating the minimal cost or containing the word Impossible.

Sample Input

3
1033 8179
1373 8017
1033 1033

Sample Output

6
7
0

3.2 解决思路

题意：寻找从素数a1到素数a2的最短素数变换路径。
分析：
    初始状态：d1d2d3d4
    目标状态：d1'd2'd3'd4'
    操作：每一位可变换为0~9其中的一个不同数字
广搜:
    注意素数的高效判断方法：素数筛。此外，如何实现数字的位变换可直接在对应的位加上一定值，
    判断其高一位是否变化，若变化，则本位的变化存在进制，影响高位，不可取。 

3.3 代码

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

bool prime[10010];
bool visited[10010];
void Find_Prime(){
    // 素数筛，初始化素数为2 
    for (int i = 2; i <= 9999; i++){
        if (prime[i]){
            // 如果i是素数，则它的倍数都不是
             for (int j = 2 * i; j <= 9999; j += i){
                prime[j] = false;
             }
        }
    } 
}

int getDigit(int x, int i){
    // 获取第i位
    int cnt = 0, k;
    while (x){
        k = x % 10;
        x /= 10;
        cnt ++;
        if (cnt == i) 
            break;
    }
    if (cnt < i) return 0; 
    else return k;
}

bool judge(int x, int newx, int i){
    if (newx < 1000 || newx > 9999 || visited[newx] || !prime[newx])
        return false;
    // 对于第i位，判断第i+1位是否变化
    if (getDigit(x, i + 1) != getDigit(newx, i + 1))
        return false;
    return true; 
}

int BFS(int a1, int a2){
    queue< pair<int, int> > q;
    memset(visited, false, sizeof(visited));
    q.push(make_pair(a1, 0));
    visited[a1] = true;
    while (!q.empty()){
        pair<int, int> x = q.front();
        q.pop();
//      printf("访问x:%d,step:%d\n", x.first,x.second);
        if (x.first == a2) return x.second;      
        for (int i = 1; i <= 4; i++){
            for (int j = 1; j < 10; j++){
                // 如果出现进位也不行 
                int newX1 = x.first + (int)pow(10, i - 1) * j;
                int newX2 = x.first - (int)pow(10, i - 1) * j;
//              printf("newX1:%d,newX2:%d\n", newX1, newX2);
                if (judge(x.first, newX1, i)){
                    q.push(make_pair(newX1, x.second + 1));
                    visited[newX1] = true;
                }
                if (judge(x.first, newX2, i)){
                    q.push(make_pair(newX2, x.second + 1));
                    visited[newX2] = true;
                }
            }
        }
    }
    return -1;
}

int main(){
    int T;
    scanf("%d", &T);
    fill(prime, prime + 10010, true);
    Find_Prime();
    while (T--){
        int a1, a2;
        scanf("%d%d", &a1, &a2);
        int res = BFS(a1, a2);
        if (res == -1) {
            printf("Impossible\n");
        }else{
            printf("%d\n", res);
        }
    }
    return 0;
}

4. POJ3087——Shuffle'm Up

4.1 题目描述

Description

A common pastime for poker players at a poker table is to shuffle stacks of chips. Shuffling chips is performed by starting with two stacks of poker chips, S₁ and S₂, each stack containing C chips. Each stack may contain chips of several different colors.

The actual shuffle operation is performed by interleaving a chip from S₁ with a chip from S₂ as shown below for C = 5:

<center> image

</center>

The single resultant stack, S₁₂, contains 2 * C chips. The bottommost chip of S₁₂ is the bottommost chip from S₂. On top of that chip, is the bottommost chip from S₁. The interleaving process continues taking the 2^nd chip from the bottom of S₂ and placing that on S₁₂, followed by the 2^nd chip from the bottom of S₁ and so on until the topmost chip from S₁ is placed on top of S₁₂.

After the shuffle operation, S₁₂ is split into 2 new stacks by taking the bottommost C chips from S₁₂ to form a new S₁ and the topmost C chips from S₁₂ to form a new S₂. The shuffle operation may then be repeated to form a new S₁₂.

For this problem, you will write a program to determine if a particular resultant stack S₁₂ can be formed by shuffling two stacks some number of times.

Input

The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of datasets that follow.

Each dataset consists of four lines of input. The first line of a dataset specifies an integer C, (1 ≤ C ≤ 100) which is the number of chips in each initial stack (S₁ and S₂). The second line of each dataset specifies the colors of each of the C chips in stack S₁, starting with the bottommost chip. The third line of each dataset specifies the colors of each of the C chips in stack S₂ starting with the bottommost chip. Colors are expressed as a single uppercase letter (A through H). There are no blanks or separators between the chip colors. The fourth line of each dataset contains 2 * C uppercase letters (A through H), representing the colors of the desired result of the shuffling of S₁ and S₂ zero or more times. The bottommost chip’s color is specified first.

Output

Output for each dataset consists of a single line that displays the dataset number (1 though N), a space, and an integer value which is the minimum number of shuffle operations required to get the desired resultant stack. If the desired result can not be reached using the input for the dataset, display the value negative 1 (−1) for the number of shuffle operations.

Sample Input

2
4
AHAH
HAHA
HHAAAAHH
3
CDE
CDE
EEDDCC

Sample Output

1 2
2 -1

4.2 解决思路

    BFS搜索即可。
    注意：问题无解的情况为出现循环状态，使用set<string>结构判断是否出现。

4.3 代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#include <set>
#include <string>
using namespace std;

char s1[110], s2[110], temp[210], s12[210];
set<string> record;

void shuffle(int n){
    int index = 0;
    for (int i = 0; i < n; i++){
        temp[index++] = s2[i];
        temp[index++] = s1[i];
    }
}

void split(int n){
    for (int i = 0; i < n; i++)
        s1[i] = temp[i];
    for (int i = n; i < 2 * n; i++)
        s2[i - n] = temp[i];
}

bool judge(int n){
    for (int i = 0; i < 2 * n; i++)
        if (temp[i] != s12[i]) return false;
    return true;
}

int main(){
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; t++){
        int n;
        scanf("%d", &n);
        scanf("%s%s%s", s1, s2, s12);
        int step = 1;
        bool flag = false;
        shuffle(n); // 初始化temp 
        while (true){
//          printf("temp:%s\n", temp);
            string str(temp);
            // 出现循环 
            if (record.find(str) != record.end()){
                break;
            }
            if (judge(n)){
                flag = true;
                break; 
            }else{
                record.insert(str);
            }
            // 对temp进行split操作
            split(n);
            // 对s1,s2进行shuffle操作
            shuffle(n);
            step ++;
        } 
        if (flag) printf("%d %d\n", t, step);
        else printf("%d %d\n", t, -1); 
    }
    return 0;
}

5. POJ3414——Pots

5.1 题目描述

Description

You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:

FILL(i) fill the pot i (1 ≤ i ≤ 2) from the tap;
DROP(i) empty the pot i to the drain;
POUR(i,j) pour from pot i to pot j; after this operation either the pot j is full (and there may be some water left in the pot i), or the pot i is empty (and all its contents have been moved to the pot j).
Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.

Input

On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).

Output

The first line of the output must contain the length of the sequence of operations K. The following K lines must each describe one operation. If there are several sequences of minimal length, output any one of them. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.

Sample Input

3 5 4

Sample Output

6
FILL(2)
POUR(2,1)
DROP(1)
POUR(2,1)
FILL(2)
POUR(2,1)

5.2 解决思路

此题深度优先+visited数组不可行：
    因为深度优先以深度为第一要素，
    不能剪掉到同一状态的不同路径中的更长的一条。
广度优先搜索：
    可行。因为广度优先是以广度为第一要素，即步数为第一要素，
    每次访问的状态必然是当前最短的路径所达到的状态。 
    
    但要解决的一个问题是：如何记录广度优先搜索的路径。
    使用链表记录前驱节点，繁琐。
    使用数组记录前驱节点的下标，递归访问前驱节点，代替链表。√ 

5.3 代码

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

struct Node{
    int id, a, b, type, arg1, arg2, step, pre; // 注意：引入step 
}nodes[100010], res; 
bool visited[110][110], flag = false;
int A, B, C, index = 0;
Node create(int id, int a, int b, int type, int arg1, int arg2, int step, int pre){
    nodes[id].a = a, nodes[id].b = b, nodes[id].type = type;
    nodes[id].arg1 = arg1, nodes[id].arg2 = arg2, nodes[id].step = step;
    nodes[id].pre = pre, nodes[id].id = id;
    return nodes[id];
} 

bool judge(Node node){
    if (node.a < 0 || node.a > A || node.b < 0 || node.b > B
    || visited[node.a][node.b]){
        return false;
    }
    return true;
}

void BFS(){
    memset(visited, false, sizeof(visited));
    queue<Node> q;
    q.push(create(index++, 0, 0, -1, -1, -1, 0, -1));
    visited[0][0] = true;
    while (!q.empty()){
        Node node = q.front();
        q.pop();
        // 判断是否到达目标状态
        if (node.a == C || node.b == C){        
            res = node;
            flag = true;
            return ;    
        } 
        // 分别进行三种操作
        Node newNode;
        // fill
        newNode = create(index++, A, node.b, 1, 1, -1, node.step + 1, node.id);
        if (judge(newNode)){
            q.push(newNode);
            visited[A][node.b] = true;
        }
        newNode = create(index++, node.a, B, 1, 2, -1, node.step + 1, node.id);
        if (judge(newNode)){
            q.push(newNode);
            visited[node.a][B] = true;
        }
        // dropout
        newNode = create(index++, 0, node.b, 2, 1, -1, node.step + 1, node.id);
        if (judge(newNode)){
            q.push(newNode);
            visited[0][node.b] = true;
        }
        newNode = create(index++, node.a, 0, 2, 2, -1, node.step + 1, node.id);
        if (judge(newNode)){
            q.push(newNode);
            visited[node.a][0] = true;
        }
        // pour
        newNode = create(index++, node.a + node.b - B < 0 ? 0 : node.a + node.b - B,
            node.a + node.b > B ? B : node.a + node.b, 3, 1, 2, node.step + 1, node.id);
        if (judge(newNode)){
            q.push(newNode);
            visited[newNode.a][newNode.b] = true;
        }
        newNode = create(index++, node.a + node.b > A ? A : node.a + node.b,
            node.a + node.b - A < 0 ? 0 : node.a + node.b - A, 3, 2, 1, node.step + 1, node.id);    
        if (judge(newNode)){
            q.push(newNode);
            visited[newNode.a][newNode.b] = true;
        }
    }
}

void printPath(Node node){
    if (node.pre == -1) return;
    // 深度优先访问 
    printPath(nodes[node.pre]);
    if (node.type == 1)
        printf("FILL(%d)\n", node.arg1);
    else if (node.type == 2)
        printf("DROP(%d)\n", node.arg1);
    else if (node.type == 3)
        printf("POUR(%d,%d)\n", node.arg1, node.arg2);
    
}
 
int main(){
    scanf("%d%d%d", &A, &B, &C);
    memset(visited, false, sizeof(visited));
    BFS();
    if (!flag){
        printf("impossible\n");
    }else{
        printf("%d\n", res.step);
        printPath(res);
    }
    
    return 0;
}