Chinaunix首页 | 论坛 | 博客
  • 博客访问: 958297
  • 博文数量: 77
  • 博客积分: 821
  • 博客等级: 军士长
  • 技术积分: 1905
  • 用 户 组: 普通用户
  • 注册时间: 2011-10-23 16:17
个人简介

学校:上海交通大学软件工程 学历:硕士 行业:从事流媒体移动开发 QQ: 412595942 邮箱:yiikai1987910@gmail.com

文章分类

全部博文(77)

文章存档

2016年(4)

2015年(15)

2014年(16)

2013年(12)

2012年(21)

2011年(9)

分类: C/C++

2014-12-27 22:11:36

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

点击(此处)折叠或打开

  1. #include "stdafx.h"
  2. #include <vector>
  3. #include <list>
  4. #include <string.h>
  5. #include <queue>

  6. using namespace std;

  7. #define WORDS (26*26*26*26)


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


  10. typedef struct
  11. {
  12.     int num;
  13.     string data;
  14. }wordsNode;

  15. bool visited[WORDS];

  16. char nextChar(char ch)
  17. {
  18.     if (ch == 'z')
  19.     {
  20.         return 'a';
  21.     }
  22.     else
  23.     {
  24.         return ++ch;
  25.     }
  26. }

  27. char perChar(char ch)
  28. {
  29.     if (ch == 'a')
  30.     {
  31.         return 'z';
  32.     }
  33.     else
  34.     {
  35.         return --ch;
  36.     }
  37. }

  38. int getWordIndex(string word)
  39. {
  40.     return ((word[0] - 'a') * (26 * 26 * 26) + (word[1] - 'a') * (26 * 26) +
  41.         (word[2] - 'a') * 26 + (word[3] - 'a'));
  42. }

  43. bool isforbid(string data,string *forbid , int num)
  44. {
  45.     for (int i = 0; i < num; i++)
  46.     {
  47.         if (data == forbid[i])
  48.         {
  49.             return true;
  50.         }
  51.     }
  52.     return false;
  53. }

  54. int minPresses(string start, string end, string forbid[])
  55. {
  56.     int totalPressNumber = 0;
  57.     queue<wordsNode> Q;
  58.     wordsNode Node;
  59.     Node.num = 0;
  60.     Node.data = start;
  61.     Q.push(Node);
  62.     while (1)
  63.     {
  64.         if (Q.empty())
  65.         {
  66.             printf("not found any words\n");
  67.             return -1;
  68.         }
  69.         wordsNode tmpnode = Q.front();
  70.         if (tmpnode.data == end)
  71.         {
  72.             printf("find words\n");
  73.             return tmpnode.num;
  74.         }
  75.         Q.pop();
  76.         tmpnode.num++;
  77.         for (int i = 0; i < 4; i++)
  78.         {
  79.             wordsNode nebNode = tmpnode;
  80.             nebNode.data[i] = nextChar(tmpnode.data[i]);
  81.             if (visited[getWordIndex(nebNode.data)] == false && !isforbid(nebNode.data,forbid,arraysize))
  82.             {
  83.                 visited[getWordIndex(nebNode.data)] = true;
  84.                 Q.push(nebNode);
  85.             }

  86.             wordsNode nebNode2 = tmpnode;
  87.             nebNode.data[i] = perChar(tmpnode.data[i]);
  88.             if (visited[getWordIndex(nebNode.data)] == false && !isforbid(nebNode.data, forbid, arraysize))
  89.             {
  90.                 visited[getWordIndex(nebNode.data)] = true;
  91.                 Q.push(nebNode);
  92.             }
  93.         }
  94.         
  95.     }
  96.     
  97. }


  98. int _tmain(int argc, _TCHAR* argv[])
  99. {
  100.     string start = "aaaa";
  101.     string end = "zzzz";
  102.     
  103.     for (int i = 0; i < WORDS; i++) {
  104.         visited[i] = false;
  105.     }

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

阅读(3423) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~