TopCoder玩耍记录-- SmartWordToy

     
    思路：4个字母的单词有26 ^ 4种组合，可以看成是26 ^ 4种状态，用BFS搜索最短步骤
    

#include "stdafx.h"
#include <vector>
#include <list>
#include <string.h>
#include <queue>

using namespace std;

#define WORDS (26*26*26*26)


string forbid[] = { "aaaz", "aaza", "azaa", "zaaa", "azzz", "zazz", "zzaz", "zzza" };
int arraysize = 8;


typedef struct
{
    int num;
    string data;
}wordsNode;

bool visited[WORDS];

char nextChar(char ch)
{
    if (ch == 'z')
    {
        return 'a';
    }
    else
    {
        return ++ch;
    }
}

char perChar(char ch)
{
    if (ch == 'a')
    {
        return 'z';
    }
    else
    {
        return --ch;
    }
}

int getWordIndex(string word)
{
    return ((word[0] - 'a') * (26 * 26 * 26) + (word[1] - 'a') * (26 * 26) +
        (word[2] - 'a') * 26 + (word[3] - 'a'));
}

bool isforbid(string data,string *forbid , int num)
{
    for (int i = 0; i < num; i++)
    {
        if (data == forbid[i])
        {
            return true;
        }
    }
    return false;
}

int minPresses(string start, string end, string forbid[])
{
    int totalPressNumber = 0;
    queue<wordsNode> Q;
    wordsNode Node;
    Node.num = 0;
    Node.data = start;
    Q.push(Node);
    while (1)
    {
        if (Q.empty())
        {
            printf("not found any words\n");
            return -1;
        }
        wordsNode tmpnode = Q.front();
        if (tmpnode.data == end)
        {
            printf("find words\n");
            return tmpnode.num;
        }
        Q.pop();
        tmpnode.num++;
        for (int i = 0; i < 4; i++)
        {
            wordsNode nebNode = tmpnode;
            nebNode.data[i] = nextChar(tmpnode.data[i]);
            if (visited[getWordIndex(nebNode.data)] == false && !isforbid(nebNode.data,forbid,arraysize))
            {
                visited[getWordIndex(nebNode.data)] = true;
                Q.push(nebNode);
            }

            wordsNode nebNode2 = tmpnode;
            nebNode.data[i] = perChar(tmpnode.data[i]);
            if (visited[getWordIndex(nebNode.data)] == false && !isforbid(nebNode.data, forbid, arraysize))
            {
                visited[getWordIndex(nebNode.data)] = true;
                Q.push(nebNode);
            }
        }

    }

}


int _tmain(int argc, _TCHAR* argv[])
{
    string start = "aaaa";
    string end = "zzzz";

    for (int i = 0; i < WORDS; i++) {
        visited[i] = false;
    }

    int value = minPresses(start, end, forbid);
    printf("Press Value is %d\n",value);
    getchar();
    return 0;
}