首页 > 试题广场 >

智能机器人

[编程题]智能机器人
  • 热度指数：182 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小阅（掌阅吉祥物）正在进行一项有趣的测试，以评估机器人在解决迷宫问题上的智能程度。因此他将机器人放在一个n*m的迷宫中，看机器人最少需要走多少步到达目的地。

输入描述:
输入包含两行，第一行代表n和m，n和m的范围是[2, 1000]，接下来n行，每行包含m个字符，代表迷宫的方格。包含四种字符：‘s’代表机器人出发点，‘e’代表机器人终点，‘.’代表可通过，‘#’代表禁止通过。


输出描述:
  输出最短需要时间，如果不能到达则输出-1。
示例1

输入

3 3
.s.
#..
e..

输出

3

说明

3*3的迷宫，从s到e，最少走3步
示例2

输入

3 3
.s.
###
e..

输出

-1

说明

3*3的迷宫，无法从s走到e
算法知识视频讲解
添加回答
JavaScript Node
穿花云烛展头像 穿花云烛展
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
   const [n,m]=(await readline()).split(' ').map(Number)
   let a=[]
   let startX,startY,endX,endY;
   for(let i=0;i<n;i++){
    const row=(await readline()).split('')
    const index=row.findIndex((i)=>i=="s"||i=="e")
    if(row[index]=="s"){startX=i;startY=index}
    else if(row[index]=="e"){endX=i;endY=index}
    a.push(row)
   }

   let found=false;
   let queue=new Array(n*m)
   let rear=0,font=0;
   let directions=[[0,1],[0,-1],[1,0],[-1,0]]
   const visited=Array.from({length:n},()=>new Array(m).fill(false))
   queue[rear++]=[startX,startY,0];
   visited[startX][startY]=true;
   while(rear>font){
    let [x,y,step]=queue[font++]
    if(x==endX&&y==endY){
        found=true
        console.log(step)
        break
    }
    for(let [dx,dy] of directions){
        let nx=x+dx
        let ny=y+dy
        if(nx>=0&&ny<m&&ny>=0&&nx<n&&!visited[nx][ny]&&a[nx][ny]!="#")
        {visited[nx][ny]=true
        queue[rear++]=[nx,ny,step+1]
        };

    }

   }
   if(!found)console.log("-1")
})();

发表于 2025-04-29 21:33:55 回复(0)
提交观点

问题信息

图 广度优先搜索(BFS)
难度：
1条回答 185浏览

热门推荐

相关试题

智能机器人

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号