http://community.topcoder.com/stat?c=problem_statement&pm=3935&rd=6532
思路：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;
-
}
TopCoder玩耍记录-- SmartWordToy
原文：http://blog.chinaunix.net/uid-24922718-id-4724310.html
