首页 > 其他分享 >Go实现迷宫搜索

Go实现迷宫搜索

时间:2023-02-18 15:11:06浏览次数:36  
标签:point int 迷宫 len queue steps 搜索 Go maze

package main

import (
   "fmt"
   "os"
)

func createMaze(filename string) [][]int {
   file, err := os.Open(filename)
   if err != nil {
      fmt.Println("文件打开错误", err)
   }
   // 读取文件第一行
   var row, col int
   fmt.Fscanf(file, "%d %d", &row, &col) //读取文件第一行
   maze := make([][]int, row)
   for i:= range maze {
      maze[i] = make([]int, col)
      for j := range maze[i] {
         fmt.Fscanf(file, "%d", &maze[i][j])
      }
   }
   return maze
}

type point struct {
   i, j int
}

// 定义 上 右 下 左 四个点位
var dirs = [4]point{
   {-1,0},{0, -1},{1, 0},{0, 1}}

// 点位相加
func (p point) add(r point) point {
   return point{p.i + r.i, p.j + r.j}
}

func (p point) at(grid [][]int) (int, bool) {
   // 行越界
   if p.i < 0 || p.i >= len(grid) {
      return 0, false
   }
   // 列越界
   if p.j < 0 || p.j >= len(grid[p.i]) {
      return 0, false
   }
   return grid[p.i][p.j], true
}

func walk(maze [][]int, start, end point) [][] int {
   // 创建一个step (走过的路)
   steps := make([][]int, len(maze))
   for i := range steps {
      steps[i] = make([]int, len(maze[i]))
   }
   // 迷宫遍历规则,上 右 下 左
   queue := []point{start} // 队列, 用于保存下一个要进行探索的点位

   for len(queue) > 0 {
      //取出队列头部元素
      cur := queue[0]
      queue = queue[1:]
      if cur == end {
         break
      }
      for _, dir := range dirs {
         next := cur.add(dir)
         // 碰见1不行 (1 代表墙)
         val, ok := next.at(maze)
         if !ok || val == 1 {
            continue
         }
         // 在steps中走过了
         val, ok = next.at(steps)
         if !ok || val != 0 {
            continue
         }
         //走回start了
         if next == start {
            continue
         }
         at, _ := cur.at(steps)
         steps[next.i][next.j] = at + 1
         queue = append(queue, next)
      }
   }
   return steps
}

func main() {
   maze := createMaze("maze/maze.in")
   steps := walk(maze, point{0, 0}, point{len(maze) - 1, len(maze[0]) - 1})
   for _, i := range steps {
      for _, j := range i {
         fmt.Printf("%2d ", j)
      }
      fmt.Println()
   }
}
6 5 //6行5列
0 1 0 0 0
0 0 0 1 0
0 1 0 1 0
1 1 1 0 0
0 1 0 0 1
0 1 0 0 0
其中1代表路不通,无法通行
程序运行结果如下:

 

标签:point,int,迷宫,len,queue,steps,搜索,Go,maze
From: https://www.cnblogs.com/xiaowenwen/p/17132674.html

相关文章

  • python Django基础
    django官网https://www.djangoproject.com/download/文档https://docs.djangoproject.com/安装Django安装官网LTS版本pipinstalldjango==3.2.15Django命令>django......
  • Golang基础-Basics
    PackagesGo语言中的包和其他语言的库或模块的概念类似,目的都是为了支持模块化、封装、单独编译和代码重用。一个包的源代码保存在一个或多个以.go为文件后缀名的源文件中,......
  • Mysql explain命令使用和搜索类型介绍
    分析语句explain是mysql中的一个指令,可以用来分析sql语句的执行计划,检测有没有使用到索引。例如:explainselect*frommvs;select_type搜索的类型table搜索的表名type搜......
  • golang流程控制if,switch分支
    if分支if单分支if条件表达式{逻辑代码}packagemainimport"fmt"funcmain(){ //varaint=9 //ifa<10{//判断a《10位true,所以为执行下面的打印a的......
  • 通过命令行从 Google Drive下载数据
    分享链接GoogleDrive的分享链接格式通常为:https://drive.google.com/file/d/<fileid>/view其中这个​​<fileid>​​就是对应文件在服务器上的唯一标识符。例如VA数据集在G......
  • 通过命令行从 Google Drive下载数据
    分享链接GoogleDrive的分享链接格式通常为:https://drive.google.com/file/d/<fileid>/view其中这个​​<fileid>​​就是对应文件在服务器上的唯一标识符。例如VA数据集在G......
  • 极兔一面:10亿级ES海量搜索狂飙10倍,该怎么办?
    文章持续更新,建议收藏起来,慢慢读!疯狂创客圈总目录博客园版为您奉上珍贵的学习资源:免费赠送:《尼恩Java面试宝典》持续更新+史上最全+面试必备2000页+面试必备+......
  • 官方文档阅读笔记(二)2.安装 Djnago
    前提条件安装Python而且Python自带轻量级数据库SQLite。设置数据库也可以不设置默认使用SQLitePostgreSQL。你也可以使用MariaDB、MySQL或者Oracle......
  • 62-CICD持续集成工具-Jenkins构建Golang的web项目
    实现Golang应用源码编译并部署安装Golang环境#编译安装[root@jenkins~]#catinstall_go.sh#!/bin/bashGO_VERSION=1.18.4URL=https://studygolang.com/dl/golang/go${......
  • 算法刷题-只出现一次的数字、输出每天是应该学习还是休息还是锻炼、将有序数组转换为
    只出现一次的数字(位运算、数组)给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。说明:你的算法应该具有线性时间复......