POJ 3009 -- Curling 2.0

2019-11-06 07:42:35

字体：大中小

来源：转载

供稿：网友

其实真的不太愿意拿博客来写题，可是这题真的错的太多次了。。。还各种找不出原因，所以一定要记录一下，也希望能够帮助同样卡了这题的童鞋们T…T

先附原题链接：http://poj.org/PRoblem?id=3009

我的思路为：DFS + 简单剪枝

错误一：

计算最小到达终点步数出错

应将该变量放入dfs函数的形参中，而不是设置为全局变量

错误二：

超时

原因：上下左右四个方向分别写了代码判断，导致相同代码重复多次，判断的次数增加了四倍

改正：利用数组d[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1}实现四个方向的移动，简化代码，加快速度

错误三：

WA。。。

数据全部测试成功

且数据还包括了讨论区中的16组数据

如下所示

(原数据) 2 1 3 2 6 6 1 0 0 2 1 0 1 1 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 1 6 1 1 1 2 1 1 3 6 1 1 0 2 1 1 3 12 1 2 0 1 1 1 1 1 1 1 1 1 3 13 1 2 0 1 1 1 1 1 1 1 1 1 1 3

输出 1 4 -1 4 10 -1

（额外数据） 1 17 1 0 0 0 0 1 0 1 0 1 1 1 0 0 3 2 0 3 6 0 0 1 1 1 1 2 3 1 1 1 0 0 1 0 0 0 1 18 14 1 0 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 3 0 1 0 1 0 1 1 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 1 0 1 1 0 1 1 1 1 1 1 0 1 1 1 1 0 1 1 0 1 1 1 0 0 1 1 0 0 2 1 1 1 1 1 1 0 1 0 1 1 0 0 0 0 0 1 1 1 1 0 0 0 1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 0 0 1 0 1 0 0 1 1 1 0 1 1 1 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0 0 1 0 0 1 1 1 0 0 1 0 1 0 1 1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 0 1 0 0 0 0 1 1 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 1 1 1 1 0 0 1 0 14 12 0 1 0 0 1 1 0 1 0 1 0 1 2 1 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 1 1 0 0 0 0 0 1 0 1 0 1 1 1 0 1 0 3 1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 9 13 1 0 1 1 0 0 1 0 0 0 0 1 1 1 1 1 0 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 1 1 0 1 1 1 1 1 1 0 1 0 1 0 1 1 0 0 0 1 0 3 1 1 0 0 1 0 1 0 1 1 0 0 0 1 2 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 1 1 0 0 1 1 0 0 1 0 0 1 0 0 0 1 1 1 0 0 1 1 1 0 2 7 3 0 1 1 0 0 1 0 1 0 0 1 2 0 4 13 1 0 1 0 1 0 0 1 1 0 1 1 3 1 0 0 1 0 1 1 0 1 1 0 0 0 0 0 2 1 0 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 1 0 1 0 0 1 14 19 0 1 0 1 1 0 0 1 1 1 1 1 0 0 1 0 0 0 3 0 0 1 1 1 2 0 1 1 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 1 1 0 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 0 1 1 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 0 0 1 1 0 0 1 1 1 1 0 1 1 0 1 1 0 0 0 1 0 1 0 1 1 1 0 0 1 0 1 1 0 0 0 1 0 0 5 4 1 0 0 1 0 3 1 1 1 2 1 0 0 1 1 1 1 0 0 0 18 6 0 1 1 0 0 1 0 0 0 0 0 1 0 1 1 1 0 0 1 0 1 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 1 1 1 1 0 0 0 1 0 0 0 1 1 0 1 0 1 2 0 0 1 0 3 1 1 1 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 1 0 19 17 1 1 1 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 0 0 0 1 0 1 0 0 1 1 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 0 1 0 0 0 0 1 1 3 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 0 1 0 1 1 1 1 0 1 0 0 0 2 1 1 1 1 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 1 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 0 1 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 1 1 0 0 1 1 1 1 0 1 0 0 1 0 1 1 1 0 0 1 0 1 0 1 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1 1 0 1 1 1 0 0 0 18 2 1 1 0 1 0 1 1 0 1 0 0 3 0 0 1 0 1 0 0 0 0 1 0 1 0 1 1 2 1 1 0 1 0 0 1 0 7 10 1 0 0 0 1 1 0 1 0 1 1 1 0 1 0 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 0 1 2 1 0 0 3 0 0 1 0 0 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 1 1 1 1 0 14 6 0 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 0 2 1 1 0 0 1 0 0 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 3 4 8 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 3 0 1 0 1 0 1 0 1 0 0 2 20 20 0 1 0 0 0 0 1 0 1 0 0 1 0 2 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 0 1 0 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 3 0 1 0 0 0 0 0 1 1 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 0 1 0 1 1 1 0 1 0 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 0 1 1 0 1 1 1 1 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1

输出 1 1 -1 -1 9 4 2 5 -1 7 6 -1 10 -1 -1 5

代码如下

#include <cstdio>#include <iostream>using namespace std;int w, h;int c[25][25], d[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};int mins = 100;void dfs(int x, int y, int s){ s++; if(s > 10) return ; for(int i = 0; i < 4; i++) { int dx = x, dy = y; bool ff = false;//用来判断block是否贴着stone dx += d[i][0]; dy += d[i][1]; while(!c[dx][dy] && 0 <= dx && dx < h && 0 <= dy && dy < w) { ff = true; dx += d[i][0]; dy += d[i][1]; } if(ff && c[dx][dy] == 1) { c[dx][dy] = 0; dfs(dx - d[i][0], dy - d[i][1], s); c[dx][dy] = 1; } if(c[dx][dy] == 3) { if(s < mins) mins = s; } } return ;}int main(){ while( scanf("%d%d", &w, &h)==2 && w && h ) { mins = 100; int x, y; for(int i = 0; i < 25; i++) for(int j = 0; j < 25; j++) c[i][j] = 0; for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) { scanf("%d", &c[i][j]); if(c[i][j] == 2) { x = i; y = j; } } c[x][y] = 0; dfs(x, y, 0); if(mins > 10) printf("-1/n"); else printf("%d/n", mins); } return 0;}

错误三至今未解决。。。

先占个坑

期待解决后再回来(●ˇ∀ˇ●)

已解决。。。

上边的代码其实是对的，之前选择了G++编译，后来改成C++编译，就成功了。。。

然0.0不知道是什么原因

不过至少自己是对的，还是蛮开心的(^_^)

上一篇：五、[LeetCode OJ]Majority Element

下一篇：CUDA Samples学习笔记1——Utilities_asyncAPI