posts - 33,  comments - 25,  trackbacks - 0
用位操作+BFS解决.基本思想如下:
给棋盘每一个状态赋予一个状态id,id计算方法是将棋盘与数的二进制表示联系起来,如题所给的数据:
bwwb
bbwb
bwwb
bwww
状态id为6585,计算方法为1*2^0+0*2^1+1*2^2..1*2^12+0*2^13..=6585(其中b代表1,w代表0)
在此基础上进行BFS搜索,首先理解一点,先点(0,0)再点(0,1)与先点(0,1)再点(0,0)对结果不造成任何影响.因此遍历棋盘的16个位置,将每次点击后的状态id利用树状结构保存.如:
                                 6585
                               /   |   \  ...
                           (0,0) (0,1)  (0,2)
                            /      |      \  ...
                         6568     6553     6646
                      ...............................
对此树进行BFS搜索,将id为0(全白)或65535(全黑)的时候则搜索成功,输出树的高度,否则输出"Impossible".
为了提高搜索效率,采用位运算,如果想将整数的二进制某一位翻转可采用id^=(1<<x)(x代表要翻转的位置)
 1 #include "assert.h"
 2 #include <iostream>
 3 #include <queue>
 4 using namespace std;
 5 
 6 const int MAX_STATE = 65536;
 7 const int ALL_WHILE_STATE = 0;
 8 const int ALL_BLACK_STATE = 65535;
 9 const int WIDTH_OF_BOARD = 4;
10 const int SIZE_OF_BOARD = WIDTH_OF_BOARD * WIDTH_OF_BOARD; // 4 * 4
11 
12 int ConvertPieceColorToInt(char color)
13 {
14     switch(color)
15     {
16     case 'b':
17         return 1;
18     case 'w':
19         return 0;
20     }
21 }
22 
23 int FlipPiece(int state_id, int position)
24 {
25     state_id ^= (1 << position);
26 
27     // up
28     if(position - 4 >= 0)
29         state_id ^= (1 << (position - 4));
30     // down
31     if(position + 4 < SIZE_OF_BOARD)
32         state_id ^= (1 << (position + 4));
33     // left
34     if(position % 4 != 0)
35         state_id ^= (1 << (position - 1));
36     // right
37     if(position % 4 != 3)
38         state_id ^= (1 << (position + 1));
39 
40     return state_id;
41 }
42 
43 int _tmain(int argc, _TCHAR* argv[])
44 {
45     int current_state_id = 0;
46     int state[MAX_STATE];
47     queue<int> search_queue;
48 
49     memset(state, -1sizeof(state));
50 
51     char color;
52 
53     for(int i = 0; i < SIZE_OF_BOARD; ++i)
54     {
55         cin >> color;
56         current_state_id += ConvertPieceColorToInt(color) << i;
57     }
58 
59     if(current_state_id == ALL_WHILE_STATE
60         || current_state_id == ALL_BLACK_STATE)
61     {
62         cout << "0" << endl;
63         return 0;
64     }
65 
66     state[current_state_id] = 0;
67     search_queue.push(current_state_id);
68 
69     int next_state_id;
70 
71     while(!search_queue.empty())
72     {
73         current_state_id = search_queue.front();
74         search_queue.pop();
75 
76         for(int i = 0; i < SIZE_OF_BOARD; ++i)
77         {
78             next_state_id = FlipPiece(current_state_id, i);
79             if(next_state_id == ALL_WHILE_STATE
80                 || next_state_id == ALL_BLACK_STATE)
81             {
82                 cout << state[current_state_id] + 1 << endl;
83                 return 0;
84             }
85             assert(next_state_id < MAX_STATE);
86             if(state[next_state_id] == -1 /* not visited */)
87             {
88                 state[next_state_id] = state[current_state_id] + 1;
89                 search_queue.push(next_state_id);
90             }
91         }
92     }
93 
94     cout << "Impossible" << endl;
95     return 0;
96 }
97 
98 

posted on 2009-03-21 10:30 肖羽思 阅读(4975) 评论(8)  编辑 收藏 引用 所属分类: POJ

FeedBack:
# re: POJ 1753 解题报告
2009-10-04 10:36 | pcfeng502
状态id为6585,计算方法为1*2^0+0*2^1+1*2^2..1*2^12+0*2^13..=6585(其中b代表1,w代表0)

按照楼主给的图(状态),这里是
1*2^0+0*2^1+0*2^2..1*2^12+1*2^13..=6585(其中b代表1,w代表0)


P.S.比较欣赏楼主这种用队列实现的清晰的写法
  回复  更多评论
  
# re: POJ 1753 解题报告
2010-07-06 17:59 | Tanky Woo
看了你的数据,学习了。
不过,那个断言你可以去掉,我测试了
没去掉:
Memory: 516K Time: 63MS
Language: C++ Result: Accepted

去掉后:
Memory: 504K Time: 16MS
Language: C++ Result: Accepted
  回复  更多评论
  
# re: POJ 1753 解题报告
2010-11-28 20:06 | talenth1
其实,把每个状态看成一个图的点,用位运算建立一个图,用spfa瞬间秒杀。。。但是比起裸宽搜还是慢点。。。。
5616K 797MS
空间比较多。。。。。  回复  更多评论
  
# re: POJ 1753 解题报告
2010-11-29 10:49 | 肖羽思
@Tanky Woo
写断言是一种习惯......  回复  更多评论
  
# re: POJ 1753 解题报告
2010-11-29 10:49 | 肖羽思
@pcfeng502

谢谢~~你能有所收获是我最欣慰的事情~
  回复  更多评论
  
# re: POJ 1753 解题报告
2010-11-29 10:50 | 肖羽思
@talenth1

谢谢提供新思路~~不过好像慢了蛮多~~不能说是瞬间秒杀了...:)  回复  更多评论
  
# re: POJ 1753 解题报告
2011-04-28 16:14 | yangyh
这算法好像有冗余吧

FlipPiece(6585,0)=6570之后就不用FlipPiece(6570,0)了吧  回复  更多评论
  
# re: POJ 1753 解题报告
2012-05-09 21:53 | hacker003
LZ的位运算计算法果然比我的普通方法快很多啊!!!
感谢分享!!!  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年3月>
22232425262728
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(3)

随笔分类

随笔档案

文章分类

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜