27 条题解

  • 0
    @ 2007-11-11 01:29:11

    凑凑热闹………………

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2007-10-17 21:15:48

    看楼下的就知道

    用BFS和DFS的区别

    BFS绝对全0ms

  • 0
    @ 2007-10-17 21:12:10

    编译通过...

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

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

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

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

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

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

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

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

    ├ 测试数据 09:答案正确... 353ms

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

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

  • 0
    @ 2006-12-16 15:49:18

    题目没错,就是缺一张图

    用迭代可以做

  • 0
    @ 2006-11-09 08:17:14

    此题出错,原题是机器人要占4个格,这里没写,也没改数据。

  • 0
    @ 2006-09-30 09:34:11

    记忆化搜索……太麻烦了!!!!!!!!!!

  • -1
    @ 2017-05-08 12:29:27
    /*
    一道很明显的bfs咯
    注意题目~
    {
    机器人的形状是一个直径1.6的球
    机器人的中心总是在格点上
    }
    所以机器人是占2*2的格子的
    所以建图要重新建立一下这个稍微需要注意一下
    还要判断一下起点终点重合的情况
    直接裸的bfs+三维v[][][]判重
    一个状态对应的表现有横坐标x,纵坐标y,面向z
    那么一个单位时间内可以做的有
    前进1,2,3个方向(这个我们可以在扩展坐标的时候加上一个*1...2...3)
    左转右转两个操作
    我们就可以直接写一下
    纯粹考验码力了
    很傻的在检验是否到达终点的时候
    返回的step忘记+1惹
    然后调了半天
    QWQ细心细心再细心
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    const int MAXN=55;
    struct node
    {
        int x,y,to,step;
    };
    queue<node> q;
    bool v[MAXN][MAXN][5];
    int a[MAXN][MAXN];
    int n,m;
    int sx,sy,tx,ty;
    int zx[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
    
    void init()
    {
        int g[MAXN][MAXN];
        char ch;
        int k=0;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>g[i][j];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(g[i][j]||g[i+1][j+1]||g[i+1][j]||g[i][j+1])
                    a[i][j]=1;
        cin>>sx>>sy>>tx>>ty;
        cin>>ch;
        if(ch=='N')
            k=0;
        else    if(ch=='E')
            k=1;
    
        else    if(ch=='S')
            k=2;
        else
            k=3;
        q.push((node){sx,sy,k,0});
        v[sx][sy][k]=1;
    }
    
    int bfs()
    {
        if(a[sx][sy]||a[tx][ty])
            return -1;
        if(sx==tx&&sy==ty)
            return 0;
        while(!q.empty())
        {
            node k=q.front();   q.pop();
            int x=k.x;  int y=k.y;  int to=k.to;    int step=k.step;
            for(int i=1;i<=3;i++)
            {
                int newx=x+zx[to][0]*i;
                int newy=y+zx[to][1]*i;
                if(newx<1||newx>n||newy<1||newy>m)
                    continue;
                if(a[newx][newy])
                    break;
                if(!v[newx][newy][to])
                {
                    v[newx][newy][to]=1;
                    q.push((node){newx,newy,to,step+1});
                    if(newx==tx&&newy==ty)
                        return step+1;
                }
            }
            for(int i=1;i<=3;i+=2)
            {
                int newto=(to+i)%4;
                if(!v[x][y][newto])
                {
                    v[x][y][newto]=1;
                    q.push((node){x,y,newto,step+1});
                }
            }
        }
        return -1;
    }
    
    int main()
    {
        init();
        cout<<bfs()<<endl;
        return 0;
    }
         
    

信息

ID
1161
难度
5
分类
搜索 点击显示
标签
(无)
递交数
436
已通过
144
通过率
33%
被复制
4
上传者