`

迷宫的最短路径

    博客分类:
  • java
 
阅读更多
代码如下:


package com.chapterOne.exercise;

import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;

/**
 * Created by yangjianzhou on 2014/8/18 21:36.
 * TODO :给定一个大小为N*M的迷宫,迷宫由通道和墙壁组成,每一步可以向邻接的上下左右四
 * 格的通道移动。求从起点到终点所需的最小步数。
 */
public class Maze {

    private static final int INF = 100000;
    private static final int N = 10;
    private static final int M = 10;
    private static char[][] mazeMatrix = {
            {'#', 'S', '#', '#', '#', '#', '#', '#', 'o', '#'},
            {'o', 'o', 'o', 'o', 'o', 'o', '#', 'o', 'o', '#'},
            {'o', '#', 'o', '#', '#', 'o', '#', '#', 'o', '#'},
            {'o', '#', 'o', 'o', 'o', 'o', 'o', 'o', 'o', 'o'},
            {'#', '#', 'o', '#', '#', 'o', '#', '#', '#', '#'},
            {'o', 'o', 'o', 'o', '#', 'o', 'o', 'o', 'o', '#'},
            {'#', '#', '#', '#', '#', '#', '#', '#', 'o', '#'},
            {'o', 'o', 'o', '#', 'o', 'o', 'o', 'o', 'o', 'o'},
            {'o', '#', '#', '#', '#', 'o', '#', '#', '#', 'o'},
            {'o', 'o', 'o', 'o', '#', 'o', 'o', 'o', 'G', '#'}
    };
    ;
    private static int xs = 0;
    private static int ys = 1;
    private static int xe = 9;
    private static int ye = 8;
    private static int[][] distance = new int[N][M];

    private static int[] xd = {1, 0, -1, 0};
    private static int[] yd = {0, 1, 0, -1};

    public static void main(String[] args) {
        initDistance();
        Maze maze = new Maze();
        int dis = maze.bfs();
        System.out.println("shortest length is : " + dis);
        printDistance();
    }

    private int bfs() {
        Queue<Point> que = new ConcurrentLinkedQueue<Point>();
        que.add(new Point(xs, ys));
        distance[xs][ys] = 0;
        while (que.size() > 0) {
            Point point = que.poll();
            if (point.getX() == xe && point.getY() == ye) {
                break;
            }
            for (int i = 0; i < 4; i++) {
                int xp = point.getX() + xd[i];
                int yp = point.getY() + yd[i];
                if (0 <= xp && xp < N && 0 <= yp && yp < M && mazeMatrix[xp][yp] != '#' && distance[xp][yp] == INF) {
                    que.add(new Point(xp, yp));
                    distance[xp][yp] = distance[point.getX()][point.getY()] + 1;
                }
            }
        }
        return distance[xe][ye];
    }

    private static void initDistance() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                distance[i][j] = INF;
            }
        }
    }

    private static void printDistance() {
        for (int i = 0; i < N; i++) {
            System.out.println();
            for (int j = 0; j < M; j++) {
                System.out.print("\t\t" + distance[i][j]);
            }
        }
    }

    class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }

        public void setX(int x) {
            this.x = x;
        }

        public void setY(int y) {
            this.y = y;
        }
    }
}




运行结果如下:


shortest length is : 22

		100000	0		100000	100000	100000	100000	100000	100000	13		100000
		2		1		2		3		4		5		100000	13		12		100000
		3		100000	3		100000	100000	6		100000	100000	11		100000
		4		100000	4		5		6		7		8		9		10		11
		100000	100000	5		100000	100000	8		100000	100000	100000	100000
		8		7		6		7		100000	9		10		11		12		100000
		100000	100000	100000	100000	100000	100000	100000	100000	13		100000
		100000	100000	100000	100000	18		17		16		15		14		15
		100000	100000	100000	100000	100000	18		100000	100000	100000	16
		100000	100000	100000	100000	100000	19		20		21		22		100000
分享到:
评论

相关推荐

    迷宫最短路径算法(dfs)

    "迷宫最短路径算法(dfs)" 迷宫最短路径问题是一个典型的搜索、遍历问题,程序设计思想在人工智能设计、机器人设计等事务中均有应用。该问题可以表述为:寻找从某一个给定的起始单元格(迷宫入口)出发,经由行...

    java实现的求迷宫最短路径算法

    本主题聚焦于使用Java实现求解迷宫最短路径的算法。在给定的压缩包中,包含两个文件:ShortPath.java和Position.java,它们分别代表了核心算法和坐标位置的数据结构。 首先,`Position.java`文件可能定义了一个类,...

    迷宫最短路径算法

    ### 迷宫最短路径算法 #### 一、引言 迷宫最短路径问题是一个典型的搜索问题,广泛应用于人工智能设计、机器人设计等领域。本文针对迷宫最短路径问题,介绍了一种新颖的算法,该算法相较于传统的深度优先搜索...

    C语言数据结构用队列求解迷宫最短路径

    从给定的代码片段来看,这是一段使用C语言实现迷宫最短路径求解的程序,主要通过队列(Queue)与栈(Stack)的数据结构来完成算法的设计与实现。下面将对这段代码涉及的关键知识点进行详细解析。 ### C语言中的数据...

    c++迷宫最短路径寻径算法

    在IT领域,迷宫最短路径寻径算法是计算机科学中的一个重要话题,它涉及到图论、数据结构和算法设计。本项目聚焦于使用C++语言实现一个能够展示迷宫及最短路径的程序,允许用户自定义迷宫。其中,核心算法可能是A*(A...

    找到一个给定的迷宫最短路径.zip_matlab 迷宫路径_matlab走迷宫_最短路径_用matlab走迷宫_迷宫最短路径

    在matlab虚拟环境,找到迷宫的最短路径

    迷宫最短路径 数据结构

    迷宫最短路径问题是一个典型的应用,涉及到数据结构如图和队列,以及算法如广度优先搜索(BFS)。这里我们将深入探讨这两个核心概念。 首先,数据结构是组织和存储数据的方式,以便更有效地进行访问和操作。在解决...

    算法相关-二维迷宫最短路径求解

    二维迷宫最短路径求解是计算机科学中的一个重要问题,主要涉及到算法设计和实现。在这个问题中,我们通常会利用图论和搜索算法来寻找从起点到终点的最短路径。VC(Visual C++)是一种常用的编程环境,用于编写控制台...

    迷宫最短路径搜索实现

    在IT领域,迷宫最短路径搜索是一种常见的问题,它涉及到算法设计与实现,特别是对于游戏开发、路径规划和网络寻径等应用。本项目采用C++编程语言,结合图形界面,提供了一种直观的方式来展示和解决这类问题。以下是...

    迷宫最短路径迷宫最短路径

    本文将深入探讨“迷宫最短路径”这一主题,主要围绕如何找到从起点到终点的最短路径。 迷宫可以被视为一个二维网格,其中每个单元格代表一个节点,可以是可通行的空地或障碍物。迷宫问题的目标是从起点(通常标记为...

    数据结构迷宫最短路径问题

    描述: 设计一个算法找一条从迷宫入口到出口的最短路径。 输入: 迷宫的行和列m n 迷宫的布局 输出: 最短路径 输入样例: 请输入迷宫的行和列:6 8 请输入迷宫的布局: 0 1 1 1 0 1 1 1 1 0 1 0 1 0 1 0 0 1 0 0 1 1...

    C++迷宫最短路径

    Eclipse下C++迷宫最短路径骨干程序,不完整

    迷宫 最短路径

    迷宫 最短路径 的C代码 算得上是有图形的

    迷宫最短路径(C#)

    本项目以C#编程语言实现了一个迷宫小程序,能够自动寻找迷宫的入口和出口路径,并计算出最短路径。下面我们将详细探讨相关的知识点。 1. **C#编程语言**: C#是一种面向对象的、类型安全的编程语言,由微软开发并...

    数据结构用队列求迷宫最短路径

    ### 数据结构用队列求迷宫最短路径 #### 知识点概述 本文将详细介绍如何使用队列这种数据结构来解决迷宫最短路径问题。该方法利用广度优先搜索(BFS)策略,通过队列存储迷宫中的各个位置,并记录下每个位置的前驱...

    迷宫最短路径问题

    根据给定的信息,本文将详细解释迷宫最短路径问题,并深入探讨其实现方式与算法原理。 ### 迷宫最短路径问题概述 在计算机科学领域,迷宫最短路径问题是一个经典的数据结构实验课题。它涉及到寻找一个二维网格迷宫...

    迷宫最短路径A*算法

    《迷宫最短路径A*算法的C++实现详解》 在计算机科学中,寻找迷宫中的最短路径是一项常见的任务,A*算法是解决此类问题的高效算法之一。A*算法结合了最佳优先搜索(如Dijkstra算法)和启发式搜索策略,能够在保证...

    迷宫最短路径数据结构源码实验报告.pdf

    "迷宫最短路径数据结构源码实验报告.pdf" 本实验报告主要关注迷宫最短路径问题的解决方案,通过数据结构和算法来实现迷宫最短路径的寻找。实验报告包括实验目的、实验要求、实现提示、算法设计、需求分析和概要设计...

    求解迷宫最短路径算法

    给出一个迷宫 2维数组 求解迷宫的最短路径问题 例如 int mg[10][10]= { {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,...

Global site tag (gtag.js) - Google Analytics