/ Vijos / 题库 / 简单的迷宫 /

题解

48 条题解

  • 1
    @ 2025-06-17 15:55:11 
    /*
ID :
LANG: C++11
TASK: maze1
 */
 
#include<iostream>
#include<string>
#include<queue>
 
using namespace std;
 
 
int main()
{
    //freopen("maze1.in", "r", stdin);
    //freopen("maze1.out", "w", stdout);
    char maze[210][80] ={};
    queue<pair<int, int>> bfs;
    typedef pair<int, int> coord;
    queue<int> dis;
    int tdis = 0;
    int W, H;
    cin >> W >> H;
    int exit[2] = {};
    for (int i = 0; i < 2 * H + 1; i ++){
        cin.get();
        cin.get(maze[i], 80);
        if (i == 0 || i == 2 * H){
            for (int j = 0; j < 2 * W + 1; j ++){
                if (maze[i][j] == ' '){
                    if (i == 0)
                        exit[0] = 1;
                    if (i == 2 * H)
                        exit[0] = 2 * H - 1;
                    exit[1] = j;
                    bfs.push(make_pair(exit[0], exit[1]));  dis.push(1);
                }
            }
        }
        else{
            if (maze[i][0] == ' '){
                exit[0] = i;    exit[1] = 1;    bfs.push(make_pair(exit[0], exit[1]));  dis.push(1);
            }
            else if (maze[i][2 * W] == ' '){
                exit[0] = i;    exit[1] = 2 * W - 1;    bfs.push(make_pair(exit[0], exit[1]));  dis.push(1);
            }
        }
    }
 
 
 
    while (!bfs.empty()){
        coord t = bfs.front();  bfs.pop();
        tdis = dis.front();    dis.pop();
        if (t.first >= 3 && maze[t.first - 1][t.second] == ' ' && maze[t.first - 2][t.second] != 'O') {//O, occupied
            maze[t.first - 2][t.second] = 'O';
            bfs.push(make_pair(t.first - 2, t.second)); dis.push(tdis + 1);
        }
        if (t.first <= 2 * H - 3 && maze[t.first + 1][t.second] == ' ' && maze[t.first + 2][t.second] != 'O') {
            maze[t.first + 2][t.second] = 'O';
            bfs.push(make_pair(t.first + 2, t.second)); dis.push(tdis + 1);
        }
        if (t.second >= 3 && maze[t.first][t.second - 1] == ' ' && maze[t.first][t.second - 2] != 'O') {
            maze[t.first][t.second - 2] = 'O';
            bfs.push(make_pair(t.first, t.second - 2)); dis.push(tdis + 1);
        }
        if (t.second <= 2 * W - 3 && maze[t.first][t.second + 1] == ' ' && maze[t.first][t.second + 2] != 'O') {
            maze[t.first][t.second + 2] = 'O';
            bfs.push(make_pair(t.first, t.second + 2)); dis.push(tdis + 1);
        }
    }
    cout << tdis << endl;
    return 0;
}
  • 0
    @ 2013-08-27 13:54:25

    坑AC率来的

  • 0
    @ 2013-03-10 21:49:44

    cow，数据还没改
    w=3,h=3，输出竟然是9

  • 0
    @ 2012-10-17 19:46:56

    样例是怎么回事？不只两个出口啊。

  • 0
    @ 2009-10-29 12:44:25

    有哪位大侠帮帮忙看一下哪里错了！！！！！！

    谢谢！！！！！！

    编译通过...

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

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

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

    ├ 测试数据 04：运行时错误...|错误号: 202

    ├ 测试数据 05：运行时错误...|错误号: 202

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

    ├ 测试数据 07：答案错误...程序输出比正确答案长

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

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

    ├ 测试数据 10：运行时错误...|错误号: 202

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

    Unaccepted 有效得分：60 有效耗时：0ms

    program p1434;

    var a:array[0..1000,0..1000]of char;

    b:array[0..1000,0..1000]of integer;

    i,j,x1,x2,y1,y2,w,h,n,m,max:integer;

    procedure sou(x,y,px,py,s:integer);

    begin

    if s=0 then begin

    if (x+1=1)and(a[x-1,y]=' ') then sou(x-1,y,x,y,s+1);

    if (y+1=1)and(a[x,y-1]=' ') then sou(x,y-1,x,y,s+1);

    end

    else begin

    if (x-2>=1)and(x-2px)and(a[x-2,y]=' ')and(a[x-1,y]=' ') then

    sou(x-2,y,x,y,s+1);

    if (x+2=1)and(y-2py)and(a[x,y-2]=' ')and(a[x,y-1]=' ') then

    sou(x,y-2,x,y,s+1);

    if (y+2

  • 0
    @ 2009-10-21 08:55:48

    楼下的是不是长宽看反了

  • 0
    @ 2009-08-30 16:46:22

    数据不是改好了吗，怎么还有人cheat？

  • 0
    @ 2009-08-29 14:09:15

    ...没办法...cheat掉..

  • 0
    @ 2009-08-27 20:21:54

    w=3 h=3

    4个出口

    输出不可能是9吧

    我输出的是4啊？

    谁能把第3点贴出来？

  • 0
    @ 2009-09-16 16:22:25

    为啥我216……

    编译通过...

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

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

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

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

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

    ├ 测试数据 06：运行时错误...|错误号: 216

    ├ 测试数据 07：运行时错误...|错误号: 216

    ├ 测试数据 08：运行时错误...|错误号: 216

    ├ 测试数据 09：运行时错误...|错误号: 216

    ├ 测试数据 10：运行时错误...|错误号: 216

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

    Unaccepted 有效得分：50 有效耗时：0ms

  • 0
    @ 2009-08-06 10:53:06

    USACO原题，copy过来就秒

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2009-08-04 19:16:27

    第三个点

    w=3 h=3

    输出应该是９

    方便大家Ａ这种不负责任的题

  • 0
    @ 2009-07-26 11:25:12

    数据真的改过了吗？第三个数据，可我怎么还总是找不到起点啊……？在USACO上是全对的……

  • 0
    @ 2009-07-20 15:28:02

    数据问题已修正

  • 0
    @ 2009-07-20 15:02:55

    +-+-+-+-+-+

    |0 0 0 0 0|

    +-+ +-+ + +

    |0 0 0|0|0|

    + +-+-+ + +

    |0|0 0 0|0

    +-+ +-+-+-+

    其实眼里是这个意思：“+”和“|”表示此路不通，“ ”表示可以通过，“0”表示经过时停留的地方（经过，步数+1）。

  • 0
    @ 2009-04-02 08:20:32

    逼我上小号CHEAT。。。。。F

  • 0
    @ 2009-02-15 14:03:34

    LS其实数据没有错，只是你的数组开小了。。

  • 0
    @ 2008-11-13 13:08:48

    floodfill

    USACO:

    Compiling...

    Compile: OK

    Executing...

    Test 1: TEST OK [0.000 secs, 564 KB]

    Test 2: TEST OK [0.011 secs, 564 KB]

    Test 3: TEST OK [0.000 secs, 564 KB]

    Test 4: TEST OK [0.000 secs, 564 KB]

    Test 5: TEST OK [0.000 secs, 560 KB]

    Test 6: TEST OK [0.130 secs, 560 KB]

    Test 7: TEST OK [0.011 secs, 560 KB]

    Test 8: TEST OK [0.011 secs, 560 KB]

    Test 9: TEST OK [0.000 secs, 560 KB]

    Test 10: TEST OK [0.011 secs, 560 KB]

    All tests OK.

    Vijos:

    编译通过...

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

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

    ├ 测试数据 03：答案错误...　├ 标准行输出

    　├ 错误行输出

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

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

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

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

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

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

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

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

    Unaccepted 有效得分：90 有效耗时：9ms

    数据是不是有误？

    只好cheat了

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2008-11-08 08:21:22

    USACO OverFencing(maze1)...

  • 0
    @ 2008-10-20 20:16:27

    我再加边界判断~都要偶数点~

    再变成四个点~- -

    结果输出变八~还是不能过~~

    WA..第三个数据.T,T

简单的迷宫

信息

ID
1434
难度
6
分类
搜索 点击显示
标签
(无)
递交数
455
已通过
106
通过率
23%
被复制
3
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1