pku 1753 Filp Game for循环+剪枝 > bfs

系统管理员 2022-08-10 00:54 11阅读 0赞

呵呵, 我用的是循环遍历, 每层加剪枝, 相当于bfs吧!

不过比bfs用的空间少的多.

<table style="width: 700px;"> 
 <tbody> 
  <tr> 
   <td>Rank:93</td> 
   <td>6223070</td> 
   <td><a rel="nofollow"></a></td> 
   <td>Memory:164K</td> 
   <td>Time:0MS</td> 
   <td>C++</td> 
   <td>1950B</td> 
   <td>2009-12-09 09:45:29</td> 
  </tr> 
 </tbody> 
</table>

\#include <cstdio> using namespace std; bool map\[4\]\[4\]; inline bool get\_bit(int num, int i) \{ if(i == -1 || i == 4) return 0; else return (num >> i)&1; \} //-1: not ok //0: all 0 //1: all 1 inline int check(int i, int j, int k, int line)//check line i, j next line, k pre line \{ int m; bool temp\[4\] = \{0\}; for(m = 3; m >= 0; --m) \{ if(get\_bit(i, m+1)^ get\_bit(i, m-1)^ get\_bit(i, m)^ get\_bit(j, m)^ get\_bit(k, m)) temp\[m\] = !map\[line\]\[m\]; else temp\[m\] = map\[line\]\[m\]; \} for(m = 1; m < 4; ++m) if(temp\[0\] != temp\[m\]) return -1; if(temp\[0\]) return 1; else return 0; \} inline int get\_bit\_count(int n) \{ int cnt = 0; for(int i = 0; i < 4; ++i) if(get\_bit(n, i)) cnt++; return cnt; \} int main() \{ int i, j, k, l; bool flagOccurWhite = false; bool flagOccurBlack = false; char ch; for(i = 0; i < 4; ++i) \{ for(j = 0; j < 4; ++j) \{ scanf("%c", &ch); if(ch == 'w') \{ map\[i\]\[j\] = true; flagOccurWhite = true; \} else \{ map\[i\]\[j\] = false; flagOccurBlack = true; \} \} getchar(); \} if(flagOccurBlack == false || flagOccurWhite == false) \{ printf("0/n"); return 0; \} int min = 17; int v1, v2, v3, v4, temp; for(i = 0; i < 16; ++i) for(j = 0; j < 16; ++j) \{ v1 = check(i, j, 0, 0); if(v1 == -1) continue; for(k = 0; k < 16; ++k) \{ v2 = check(j, k, i, 1); if(v2 == -1 || v2 != v1) continue; for(l = 0; l < 16; ++l) \{ v3 = check(k, l, j, 2); if(v3 == -1 || v3 != v2) continue; v4 = check(l, 0, k, 3); if(v4 == -1 || v4 != v3) continue; temp = get\_bit\_count(i)+get\_bit\_count(j) +get\_bit\_count(k)+get\_bit\_count(l); if(temp < min) min = temp; \} \} \} if(min < 17) printf("%d/n", min); else printf("Impossible/n"); return 0; \}

code2:

\#include <iostream> \#include <queue> using namespace std; int n; bool visited\[65536\]; int step\[65536\]; inline void change(int& num, int i) \{ num ^= (1<<i); if(i%4 != 0) num ^= (1<<(i-1)); if(i%4 != 3) num ^= (1<<(i+1)); if(i/4 != 0) num ^= (1<<(i-4)); if(i/4 != 3) num ^= (1<<(i+4)); \} int bfs() \{ memset(visited, 0, sizeof(visited)); memset(step, 0, sizeof(step)); queue<int> q; q.push(n); visited\[n\] = true; while(!q.empty()) \{ int v = q.front(); visited\[v\] = true; q.pop(); for(int i = 0; i < 16; ++i) \{ int temp = v; change(temp, i); if(temp == 0 || temp == 65535) return step\[v\]+1; if(!visited\[temp\]) \{ q.push(temp); visited\[temp\] = true; step\[temp\] = step\[v\]+1; \} \} \} return -1; \} int main() \{ char ch; for(int i = 0; i < 4; ++i) for(int j = 0; j < 4; ++j) \{ cin >> ch; if(ch == 'w') n += 1; n <<= 1; \} n >>= 1; //move only 15 times if(n == 0 || n == 65535) \{ printf("0/n"); return 0; \} int ret = bfs(); if(ret != -1) printf("%d/n", ret); else printf("Impossible/n"); return 0; \}

总结一下:

这种用16位的二进制数表示4\*4方格所有状态的方法也很巧妙.

具体说来,用16位二进制数表示一个4\*4方格的当前状态,  
通过对这个16位二进制数的任意一位进行变化后,进入队列.

不过效率显然不如用for循环+剪枝来的快, 因为先对一行的状态  
进行遍历, 剪枝会多一些.

可以发现, bfs的精髓是: 采用二进制数做状态的转移的量. bfs不过是  
保存状态和寻找他的下一状态.