pku 1324 Holedox Moving 冬眠蛇 bfs+状态保存+强剪枝

梦里梦外; 2022-08-10 08:55 2阅读 0赞

<table style="width: 700px;"> 
 <tbody> 
  <tr> 
   <td>Rank:107</td> 
   <td><a href="http://writeblog.csdn.net/status?user_id=xiaofengsheng&amp;problem_id=1324&amp;result=0" rel="nofollow"><span style="font-size: small;">6234457(4)</span></a></td> 
   <td><a href="http://writeblog.csdn.net/userstatus?user_id=xiaofengsheng" rel="nofollow"><span style="font-size: small;">xiaofengsheng</span></a></td> 
   <td><span style="font-size: small;">Memory:7600K</span></td> 
   <td><span style="font-size: small;">Time:688MS</span></td> 
   <td><a href="http://writeblog.csdn.net/showsource?solution_id=6234457" rel="nofollow"><span style="font-size: small;">C++</span></a></td> 
   <td><span style="font-size: small;">4275B</span></td> 
   <td><span style="font-size: small;">2009-12-11 23:45:18</span></td> 
  </tr> 
 </tbody> 
</table>

剪枝部分使用maxStep, minStep吸纳了下面博客里提到的算法:

[http://hi.baidu.com/jlw686/blog/item/7f100cb1b3d0c651082302fc.html][http_hi.baidu.com_jlw686_blog_item_7f100cb1b3d0c651082302fc.html]

\#include <iostream> \#include <queue> using namespace std; \#define MAX\_STATE (1<<14) int n, m, L, K; int map\[20\]\[20\]; bool visited\[20\]\[20\]\[MAX\_STATE\]; int step\[20\]\[20\]; struct State\{ short x, y; short state; short step; State(short \_\_x, short \_\_y, short \_\_state, short \_\_step) \{x = \_\_x; y = \_\_y; state = \_\_state; step = \_\_step;\} \}; struct Point\{ short x, y; Point(short \_\_x, short \_\_y)\{x = \_\_x; y = \_\_y;\} Point()\{\} \}; short curState; Point head\[8\]; short mask; int dx\[\] = \{-1, 0, 1, 0\}; int dy\[\] = \{0, -1, 0, 1\}; int minStep, maxStep; bool visited2\[20\]\[20\]; short step2\[20\]\[20\]; inline bool ok2(int x, int y) \{ if(x < 0 || x >= m || y < 0 || y >= n || map\[y\]\[x\] == true) return false; return true; \} int getMin() \{ memset(visited2, 0, sizeof(visited2)); memset(step2, 0, sizeof(step2)); queue<Point> q; q.push(Point(head\[0\].x, head\[0\].y)); visited2\[head\[0\].y\]\[head\[0\].x\] = true; while(!q.empty()) \{ Point p = q.front(); q.pop(); for(int i = 0; i < 4; ++i) \{ int tempx = p.x+dx\[i\], tempy = p.y+dy\[i\]; if(ok2(tempx, tempy) && !visited2\[tempy\]\[tempx\]) \{ if(tempx == 0 && tempy == 0) return step2\[p.y\]\[p.x\]+1; q.push(Point(tempx, tempy)); step2\[tempy\]\[tempx\] = step2\[p.y\]\[p.x\]+1; visited2\[tempy\]\[tempx\] = true; \} \} \} return -1; \} int getMax() \{ memset(visited2, 0, sizeof(visited2)); memset(step2, 0, sizeof(step2)); queue<Point> q; q.push(Point(head\[0\].x, head\[0\].y)); for(int i = 0; i < L; ++i) visited2\[head\[i\].y\]\[head\[i\].x\] = true; while(!q.empty()) \{ Point p = q.front(); q.pop(); for(int i = 0; i < 4; ++i) \{ int tempx = p.x+dx\[i\], tempy = p.y+dy\[i\]; if(ok2(tempx, tempy) && !visited2\[tempy\]\[tempx\]) \{ if(tempx == 0 && tempy == 0) return step2\[p.y\]\[p.x\]+1; q.push(Point(tempx, tempy)); step2\[tempy\]\[tempx\] = step2\[p.y\]\[p.x\]+1; visited2\[tempy\]\[tempx\] = true; \} \} \} return -1; \} //行n, 列m inline bool ok(int x, int y, State s) \{ if(x < 0 || x >= m || y < 0 || y >= n || map\[y\]\[x\] == true) return false; int curx = s.x, cury = s.y; for (int i = 0; i < L-1; ++i) \{ int dir = (s.state>>(i\*2))&(0x0003); curx += dx\[dir\], cury += dy\[dir\]; if(curx == x && cury == y) return false; \} return true; \} int bfs() \{ memset(visited, 0, sizeof(visited)); queue<State> q; q.push(State(head\[0\].x, head\[0\].y, curState, 0)); visited\[head\[0\].y\]\[head\[0\].x\]\[curState\] = true; while (!q.empty()) \{ State s = q.front(); q.pop(); for(short i = 0; i < 4; ++i) \{ int tempx = s.x + dx\[i\], tempy = s.y + dy\[i\]; if(s.step + tempx + tempy + 1 > maxStep) continue; if(ok(tempx, tempy, s)) \{ if(tempx == 0 && tempy == 0) return s.step+1; short temp = s.state; temp <<= 2; temp |= (i+2)%4; temp &= mask; if(!visited\[tempy\]\[tempx\]\[temp\]) \{ q.push(State(tempx, tempy, temp, s.step+1)); visited\[tempy\]\[tempx\]\[temp\] = true; \} \} \} \} return -1; \} int main() \{ int cnt = 0; while(scanf("%d%d%d", &n, &m, &L), n) \{ curState = 0; scanf("%hd%hd", &head\[0\].y, &head\[0\].x); head\[0\].y--; head\[0\].x--; for(int i = 1; i < L; ++i) \{ scanf("%hd%hd", &head\[i\].y, &head\[i\].x); head\[i\].y--; head\[i\].x--; if(head\[i\].y == head\[i-1\].y) \{ if(head\[i-1\].x < head\[i\].x) curState |= (2<<((i-1)\*2)); \} else \{ if(head\[i\].y < head\[i-1\].y) curState |= (1<<((i-1)\*2)); else curState |= (3<<((i-1)\*2)); \} \} int x, y; memset(map, 0, sizeof(map)); scanf("%d", &K); for(int i = 0; i < K; ++i) \{ scanf("%d%d", &y, &x); map\[--y\]\[--x\] = true; \} if(head\[0\].x == 0 && head\[0\].y == 0) printf("Case %d: 0/n", ++cnt); else \{ minStep = getMin(); if(minStep == -1) printf("Case %d: -1/n", ++cnt); else \{ maxStep = getMax(); if(maxStep == -1) maxStep = INT\_MAX; if(maxStep == minStep) printf("Case %d: %d/n", ++cnt, minStep); else \{ mask = (1<<((L-1)\*2))-1; printf("Case %d: %d/n", ++cnt, bfs()); \} \} \} \} return 0; \}

[http_hi.baidu.com_jlw686_blog_item_7f100cb1b3d0c651082302fc.html]: http://hi.baidu.com/jlw686/blog/item/7f100cb1b3d0c651082302fc.html