java - 有约束的图中两个坐标点之间的最短路径数

Question

我得到了几个坐标点:

1. 来源 (0,0)

2. 目的地 (m,n)

3. 一组坐标点S = {(x,y)这样 0 < x < m和 0 < y < n}

目标是找出(0,0)之间的最短路径数和 (m,n)这样集合中的任何点 S在这些路径中从未遇到过。我如何找到它？

Answer 1

这里有一个 C# 解决方案，但可以轻松转换为 Java。希望您会发现它很有用。

using System;
using System.Collections.Generic;
using System.Drawing;

namespace Game
{
    class Program
    {
        /// <summary>
        /// Find a matrix with all possible optimum paths from point A to point B
        /// </summary>
        /// <param name="rows">Rows of the matrix</param>
        /// <param name="cols">Cols of the matrix</param>
        /// <param name="points">Obstacles location</param>
        /// <param name="moves">Allowed moves</param>
        /// <param name="matrix">Resulting matrix</param>
        /// <param name="A">Starting point</param>
        /// <param name="B">Ending point</param>
        private static void FindMatrix(int rows, int cols, List<Point> points, List<Point> moves, out List<List<int>> matrix, out Point A, out Point B)
        {
            matrix = new List<List<int>>();
            A = new Point(-1, -1);
            B = new Point(-1, -1);
            //Init values of the matrix
            for (int row = 0; row <= rows; row++)
            {
                matrix.Add(new List<int>());
                for (int col = 0; col <= cols; col++)
                    matrix[matrix.Count - 1].Add(0);
            }
            var index = 0;
            while ((index < points.Count) && (points[index].Y >= 0) && (points[index].Y <= rows) && (points[index].X >= 0) && (points[index].X <= cols))
            {
                matrix[points[index].Y][points[index].X] = -1;
                index++;
            }
            if ((index == points.Count) && (matrix[0][0] == 0) && (matrix[rows][cols] == 0))
            {
                A.X = 0;
                A.Y = 0;
                B.X = cols;
                B.Y = rows;
            }
            if ((A.X >= 0) && (A.Y >= 0) && (B.X >= 0) && (B.Y >= 0)) //To check if points A and B exist in the board
            {
                var pairs = new List<Point>[2] { new List<Point>(), new List<Point>() };
                int level = 0;
                index = 0;
                pairs[index].Add(A);
                while ((pairs[index].Count > 0) && (pairs[index][pairs[index].Count - 1] != B))
                {
                    pairs[Math.Abs(1 - index)].Clear();
                    level++;
                    foreach (var pair in pairs[index])
                        foreach (var move in moves) //Test all possible moves
                            if ((pair.Y + move.Y >= 0) && (pair.Y + move.Y < matrix.Count) && (pair.X + move.X >= 0) && (pair.X + move.X < matrix[pair.Y + move.Y].Count) && (matrix[pair.Y + move.Y][pair.X + move.X] == 0)) //Inside the boundaries? Not visited before?
                            {
                                pairs[Math.Abs(1 - index)].Add(new Point(pair.X + move.X, pair.Y + move.Y));
                                matrix[pair.Y + move.Y][pair.X + move.X] = level;
                            }
                    index = Math.Abs(1 - index);
                }
                matrix[A.Y][A.X] = 0;
            }
        }

        /// <summary>
        /// Finds all possible optimum paths from point A to point B in a matix with obstacles
        /// </summary>
        /// <param name="matrix">Matrix with obstacles</param>
        /// <param name="moves">Allowed moves</param>
        /// <param name="A">Starting point</param>
        /// <param name="B">Ending point</param>
        /// <param name="result">Resulting optimum paths</param>
        /// <param name="list">Temporary single optimum path</param>
        private static void WalkMatrix(List<List<int>> matrix, List<Point> moves, Point A, Point B, ref List<List<Point>> result, ref List<Point> list)
        {
            if ((list.Count > 0) && (list[list.Count - 1] == B)) //Stop condition
            {
                result.Add(new List<Point>(list));
            }
            else
            {
                foreach (var move in moves)
                    if ((A.Y + move.Y >= 0) && (A.Y + move.Y < matrix.Count) && (A.X + move.X >= 0) && (A.X + move.X < matrix[A.Y + move.Y].Count) && (matrix[A.Y + move.Y][A.X + move.X] == matrix[A.Y][A.X] + 1)) //Inside the boundaries? Next step?
                    {
                        list.Add(new Point(A.X + move.X, A.Y + move.Y)); //Store temporary cell
                        WalkMatrix(matrix, moves, list[list.Count - 1], B, ref result, ref list);
                        list.RemoveAt(list.Count - 1); //Clean temporary cell
                    }
            }
        }

        public static List<List<Point>> FindPaths(int rows, int cols, List<Point> points)
        {
            var result = new List<List<Point>>();
            var moves = new List<Point> { new Point(1, 0), new Point(0, 1), new Point(-1, 0), new Point(0, -1) }; //Right, Down, Left, Up (clockwise)
            List<List<int>> matrix; //Matrix temporary representation to store all possible optimum paths
            Point A; //Starting point
            Point B; //Ending point
            FindMatrix(rows, cols, points, moves, out matrix, out A, out B);
            if ((A.X >= 0) && (A.Y >= 0) && (B.X >= 0) && (B.Y >= 0)) //To check if points A and B exist
            {
                List<Point> list = new List<Point>();
                list.Add(A);
                WalkMatrix(matrix, moves, A, B, ref result, ref list);
            }
            return result;
        }

        static void Main(string[] args)
        {
            var points = new List<Point>
            {
                new Point(3, 2),
                new Point(4, 2),
                new Point(5, 2),
                new Point(3, 3),
                new Point(4, 3),
                new Point(5, 3),
                new Point(3, 4),
                new Point(4, 4),
                new Point(5, 4)
            };
            List<List<Point>> paths = FindPaths(5, 10, points); //path.Count store the quantity of optimum paths
        }
    }
}