pku 3009 Curling 2.0 DFS+剪枝

本是古典何须时尚 2022-08-09 15:59 154阅读 0赞

开始用第一种方式写的,总是WA,郁闷,至今还不知为啥,希望高人指点,用第二种方式写后,AC.

if(step > 10)  
return;

这样剪枝后,168k, 250ms.

再剪枝,

if(step > 10 || step >= minStep)  
return;

168k 79ms.

//WA \#include <iostream> using namespace std; int startx, starty, endx, endy; int w, h; int map\[22\]\[22\]; int minCount; struct Point\{ int x,y; \}; bool ok(int x, int y, Point& p, int c) \{ int i; p.x = x, p.y = y; if(c == 0) \{ for(i = x-1; i >= 0; i--) if(map\[y\]\[i\] == 1 || map\[y\]\[i\] == 3) break; if(i == -1 || i == x-1&&map\[y\]\[i\] == 1) return false; else if(map\[y\]\[i\] == 3) p.x = i; else p.x = i+1; \} else if(c == 1) \{ for(i = y-1; i >= 0; i--) if(map\[i\]\[x\] == 1 || map\[i\]\[x\] == 3) break; if(i == -1 || i == y-1&&map\[i\]\[x\] == 1) return false; else if(map\[i\]\[x\] == 3) p.y = i; else p.y = i+1; \} else if(c == 2) \{ for(i = x+1; i < w; ++i) if(map\[y\]\[i\] == 1 || map\[y\]\[i\] == 3) break; if(i == w|| i == x+1&&map\[y\]\[i\]==1) return false; else if(map\[y\]\[i\] == 3) p.x = i; else p.x = i-1; \} else \{ for(i = y+1; i < h; ++i) if(map\[i\]\[x\] == 1 || map\[i\]\[x\] == 3) break; if(i == h || i == y+1&&map\[i\]\[x\]==1) return false; else if(map\[i\]\[x\] == 3) p.y = i; else p.y = i-1; \} return true; \} void dfs(int x, int y, int n) \{ if(n > 10) return; if(x == endx && y == endy) \{ if(n < minCount) minCount = n; return; \} for(int i = 0; i < 4; ++i) \{ Point p; if(ok(x, y, p, i)) \{ //printf("newx=%d,newy=%d/n", p.x, p.y); if(i == 0) map\[p.y\]\[p.x-1\] = 0; else if(i == 1) map\[p.y-1\]\[p.x\] = 0; else if(i == 2) map\[p.y\]\[p.x+1\] = 0; else map\[p.y+1\]\[p.x\] = 0; dfs(p.x, p.y, n+1); if(i == 0) map\[p.y\]\[p.x-1\] = 1; else if(i == 1) map\[p.y-1\]\[p.x\] = 1; else if(i == 2) map\[p.y\]\[p.x+1\] = 1; else map\[p.y+1\]\[p.x\] = 1; \} \} \} int main() \{ //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); while(scanf("%d%d", &w, &h) && w) \{ for (int i = 0; i < h; ++i) for (int j = 0;j < w; ++j) \{ scanf("%d", &map\[i\]\[j\]); if(map\[i\]\[j\] == 2) startx = j, starty = i; else if(map\[i\]\[j\] == 3) endx = j, endy = i; \} minCount = 0x7fffffff; dfs(startx, starty, 0); if(minCount == 0x7fffffff || minCount > 10) printf("-1/n"); else printf("%d/n", minCount); \} return 0; \} //AC \#include <iostream> using namespace std; int dx\[\] = \{-1, 0, 1, 0\}; int dy\[\] = \{0, -1, 0, 1\}; int w, h; int map\[20\]\[20\]; int startx, starty; int minStep; enum square\_t\{ VACANT = 0, BLOCK, START, GOAL \}; inline bool ok(int x, int y) \{ if(x < 0 || x >= w || y < 0 || y >= h) return false; return true; \} void dfs(int x, int y, int step) \{ if(step > 10 || step >= minStep) return; for(int i = 0; i < 4; ++i) \{ int tempx = x, tempy = y; if(!ok(tempx+dx\[i\], tempy+dy\[i\]) || map\[tempy+dy\[i\]\]\[tempx+dx\[i\]\] == BLOCK) continue; while(true) \{ if(!ok(tempx+dx\[i\], tempy+dy\[i\])) break; if(map\[tempy+dy\[i\]\]\[tempx+dx\[i\]\] == GOAL) \{ if(step < minStep) minStep = step+1; return; \} if(map\[tempy+dy\[i\]\]\[tempx+dx\[i\]\] == BLOCK) \{ map\[tempy+dy\[i\]\]\[tempx+dx\[i\]\] = VACANT; dfs(tempx, tempy, step+1); map\[tempy+dy\[i\]\]\[tempx+dx\[i\]\] = BLOCK; break; \} tempx += dx\[i\]; tempy += dy\[i\]; \} \} \} int main() \{ while(scanf("%d%d", &w, &h) && w) \{ for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) \{ scanf("%d", &map\[i\]\[j\]); if(map\[i\]\[j\] == 2) startx = j, starty = i; \} minStep = 11; dfs(startx, starty, 0); if(minStep < 11) printf("%d/n", minStep); else printf("-1/n"); \} return 0; \}