/ Vijos / 题库 / 渡河 /

题解

39 条题解

  • 0
    @ 2008-10-22 18:45:39

    我的大招就是bfs合并区域之后用repeat修正路径长度，直到不能修正。

  • 0
    @ 2008-10-21 20:43:48

    不是很快.....见识到了fillchar的力量......队列不用不断初始的...

  • 0
    @ 2008-10-21 14:33:32

    造图的不会超内存吗？

  • 0
    @ 2008-10-20 22:09:34

    利用双重BFS..

    进行拓展结点

    保证主队列中结点的值为递增。

    另一个队列对(x1,y1)→(x2,y2)代价为0时进行拓展。

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 72ms

    ├ 测试数据 06：答案正确... 134ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 41ms

    ├ 测试数据 10：答案正确... 181ms

    速度还算好..

  • 0
    @ 2008-10-20 21:37:39

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 72ms

    ├ 测试数据 06：答案正确... 134ms

    ├ 测试数据 07：答案正确... 275ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 197ms

    ├ 测试数据 10：答案正确... 134ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：812ms

  • 0
    @ 2008-10-20 21:32:11

    评测机很不稳定。。。

    Lora第一次评测0分，第二次90，Puppy来了，100...

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 56ms

    ├ 测试数据 06：答案正确... 166ms

    ├ 测试数据 07：答案正确... 228ms

    ├ 测试数据 08：答案正确... 150ms

    ├ 测试数据 09：答案正确... 275ms

    ├ 测试数据 10：答案正确... 150ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：1025ms

  • 0
    @ 2008-10-20 21:19:36

    floodfill，相同颜色为一个点，相邻点连边，求SPFA即可

  • 0
    @ 2008-10-20 18:00:54

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 150ms

    ├ 测试数据 06：答案正确... 197ms

    ├ 测试数据 07：答案正确... 197ms

    ├ 测试数据 08：答案正确... 244ms

    ├ 测试数据 09：答案正确... 197ms

    ├ 测试数据 10：答案正确... 212ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：1197ms

    floodfill

    用BFS好写

  • 0
    @ 2008-10-20 17:36:39

    floodfill，我们可以解释成相邻块染色。

    本题，可以建立一个这样的关系：第x块与第y块是河与陆地的关系，

    从i块到j块要通过几次转换块，然后只需知道边界是哪些块就可以了。

    至于染色，不推荐遍历（虽然编起来简单），推荐用并查集+优化结构，至于着么在矩阵中用并查集，我是把那个矩阵拉成了一条链，算然丑，但算是可以做了。

  • 0
    @ 2008-10-20 13:09:46

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 119ms

    ├ 测试数据 06：答案正确... 134ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 150ms

    ├ 测试数据 09：答案正确... 166ms

    ├ 测试数据 10：答案正确... 134ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：703ms

  • 0
    @ 2008-10-20 13:07:03

    FLOODFILL

  • 0
    @ 2008-10-20 09:43:38

    最外面一圈可以为1啊...

  • 0
    @ 2008-10-19 23:12:33

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 56ms

    ├ 测试数据 06：答案正确... 181ms

    ├ 测试数据 07：答案正确... 119ms

    ├ 测试数据 08：答案正确... 150ms

    ├ 测试数据 09：答案正确... 103ms

    ├ 测试数据 10：答案正确... 103ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：712ms

    \\\\\\\\\\\\\\\\\\\

    floodfill sudu

  • 0
    @ 2008-10-19 21:23:30

    什么是floodfill？？？大牛能贴出来吗？谢谢了

  • 0
    @ 2008-10-19 19:55:36

    floodfill算法

  • 0
    @ 2008-10-19 17:16:24

    DFS会不会溢出？我觉得BFS保险一点。

    输入里面有询问河流的，我WA了一个点……

  • 0
    @ 2008-10-19 16:36:32

    广搜+深搜应该能够过吧

  • 0
    @ 2008-10-19 14:20:41

    .........

  • 0
    @ 2008-10-17 14:18:18

    有趣?你们两个,始终是你们两个

渡河

信息

ID
1468
难度
7
分类
搜索 | 数据结构 | 并查集 点击显示
标签
递交数
606
已通过
99
通过率
16%
被复制
2
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1