Hop — Don’t Walk!

Problem Description
KERMIT THE FROG is a classic video game with a simple control and objective but requires a good deal of thinking.
You control an animated frog that can walk and hop, in both forward and backward directions. The frog stands in a space between an otherwise a contiguous line of tiles. Each tile is painted black on one side, and white on the other. The frog can walk (forward, or backward) over an adjacent tile (in front or behind him.)
When the frog walks over a tile, the tile slides to the space where the frog was standing. For example, in the adjacent figure, the frog has two tiles behind him, and three in front. We’ll use the notation BWFBBW to refer to this situation where F refers to the space (where the frog is standing,) B is a tile with its black face showing, while W is a tile with its white face showing. The forward direction is from left to right. If the frog were to walk forward, the resulting situation is BWBFBW. Similar behavior when the frog walks backward, the tile behind the frog slides to where the frog was standing. The frog can also hop over the tiles. The frog can hop over an adjacent tile landing on the tile next to it. For example, if the frog was to hop backward, it would land on the first (left-most) tile, and the tile would jump to the space where the frog was standing. In addition, the tile would flip sides. For example, hopping backward in the figure would result in the situation: FWWBBW. We challenge you to write a program to determine the minimum number of moves (walks or hops) to transform one tile configuration into another.

 

Input
Your program will be tested on one or more test cases. Each test case is specified on a single line that specifies string S representing the initial tile arrangement. S is a non-empty string and no longer than 100 characters and is made of the letters ’B’, ’W’, and exactly one ’F’. The last line of the input file has one or more ’-’ (minus) characters.
 

Output
For each test case, print the following line:
k. M
Where k is the test case number (starting at one,) and M is the minimum number of moves needed to transform the given arrangement to an arrangement that has no white tile(s) between any of its black tiles . The frog can be anywhere. M is -1 if the problem cannot be solved in less than 10 moves.
Note: There is a blank space before M.
 

Sample Input
WWBBFBW
WWFBWBW
FWBBWBW
---
 

Sample Output
1. 0
2. 1
3. 2

题意：青蛙可向前或向后走一步，走后，青蛙所在位置的砖滑到青蛙没跳前的位置。青蛙也可以向前跳或向后跳，跳一次能跳过2个砖，


青蛙所在位置的砖翻转后滑到青蛙没跳前的位置。求青蛙在十个动作之内，使任意两个黑砖之间没白砖的最小步数。



#include<stdio.h>
#include<string.h>
#define maxn 300000
int ans, len;
char state[maxn][100];
char step[maxn], f[maxn];
int check(int depth)
{
    int i, j, x, y;
    for (i = 0, j = len - 1, x = y = -1; i < len; i++, j--)
    {
        if (state[depth][i] == 'B' && x == -1)
        {
            x = i;
        }
        if (state[depth][j] == 'B' && y == -1)
        {
            y = j;
        }
    }
    if (x != -1 && y != -1)
    {
        for (i = x + 1; i < y; i++)
        {
            if (state[depth][i] == 'W')
            {
                return 0;
            }
        }
    }
    return 1;
}
void swap(int depth, int i, int j)
{
    state[depth][i] ^= state[depth][j];
    state[depth][j] ^= state[depth][i];
    state[depth][i] ^= state[depth][j];
}
void hopf(int depth, int i)
{
    swap(depth, i, i + 2);
    state[depth][i] = (state[depth][i] == 'B') ? 'W' : 'B' ;
}
void hopb(int depth, int i)
{
    swap(depth, i, i - 2);
    state[depth][i] = (state[depth][i] == 'B') ? 'W' : 'B' ;
}
void bfs()
{
    int head = 0, tial = 1, h;
    if (check(0))
    {
        ans = 0;
        return;
    }
    while (head < tial)
    {
        if (step[head] >= 9)
        {
            return;
        }
        h = f[head];
        if (h + 1 < len)
        {        
            strcpy(state[tial], state[head]);
            swap(tial, h, h + 1);
            step[tial] = step[head] + 1;
            f[tial] = h + 1;
            if (check(tial))
            {
                ans = step[tial];
                return;
            }
            tial++;
        }
        if (h - 1 >= 0)
        {
            strcpy(state[tial], state[head]);
            swap(tial, h, h - 1);
            step[tial] = step[head] + 1;
            f[tial] = h - 1;
            if (check(tial))
            {
                ans = step[tial];
                return;
            }
            tial++;
        }
        if (h + 2 < len)
        {
            strcpy(state[tial], state[head]);
            hopf(tial, h);
            step[tial] = step[head] + 1;
            f[tial] = h + 2;
            if (check(tial))
            {
                ans = step[tial];
                return;
            }
            tial++;
        }
        if (h - 2 >= 0)
        {
            strcpy(state[tial], state[head]);
            hopb(tial, h);
            step[tial] = step[head] + 1;
            f[tial] = h - 2;
            if (check(tial))
            {
                ans = step[tial];
                return;
            }
            tial++;
        }
        head++;
    }
}
int main()
{
    int i, j, k = 0;
    char s[100];
    while (scanf("%s", s), s[0] != '-')
    {
        k++;
        ans = 10;
        for (i = 0; (state[0][i] = s[i]) != 0; i++)
        {
            if (s[i] == 'F')
            {
                j = i;
            }
        }
        len = i;
        strcpy(state[0], s);
        step[0] = 0;
        f[0] = j;
        bfs();        
        printf("%d. %d\n", k, ans < 10 ? ans : -1);
    }
}