我一直在考虑几个坐标点：

I have been given few coordinate points :

源（0,0）

目标（M，N）

一组坐标点 S = {（X，Y），使得 0℃ X - LT;米和 0℃ Y'LT; N}

目标是找出最短路径之间的的数量（0,0）和（M，N）这样，在设定的任何一点取值再也不能在这些路径中遇到。我怎么觉得呢？

Objective is to find out the number of shortest paths between (0,0) and (m,n) such that any point in the set S is never encountered in these paths. How do i find it?

推荐答案

在这里，你必须在C＃中的解决方案，但可以很容易地转换为Java。希望你会发现它是有用的。

Here you have a solution in C# but can converted easily to Java. Hopefully you will find it useful.

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
        }
    }
}