Longest Path in a grid [closed]

StackOverflow https://stackoverflow.com/questions/17133425

  •  31-05-2022
  •  | 
  •  

Question

Given a grid G. Each cell can contain numbers [0 - 9] inclusive or an upper case alphabetical letter (say Z); we can start with the upper left corner. Then if the cell number we are on is a, we can allowed to move exactly a cells up, down left or right. Until we reach an alphabetical letter then we stop. Given these rules, we want to find the maximum path from the start till we get out of the grid. If the path is infinite, print "-1";

Was it helpful?

Solution

Ok, to solve using dynamic programming the problem needs to have these essential properties -

  1. Optimal substructure - optimal sol. to smaller problems leads to optimal sol. to larger problems.
  2. Overlapping subproblems - we can store answers and reuse them (this is what gives dynamic programming efficiency, otherwise complexity would be exponential).

That was some theory, coming back the maze problem. Since you want the MAXIMUM path from the start to end. This is a NP-Hard problem & no polynomial solution exists. A General maximum path problem in a graph with positive weights is as simple as Travelling Salesmen problem where we visit all nodes before reaching destination as longest path includes all vertices.

So the approach you take is this (also mentioned in wiki link) -

  1. Consider your maze as a graph. Perform a DFS on it which will result in a DFS-tree.
  2. Use the sequence of root-to-leaf paths of the depth-first search tree, in the order in which they were traversed by the search, to construct a path decomposition of the graph, with pathwidth d. i.e. Traverse this DFS tree and one path would be there from root-to-leaf which starts from a and ends at z.
  3. Apply dynamic programming to this path decomposition to find a longest path.

OTHER TIPS

The grid forms a directed graph, with possible cycles. For each cell in the grid, you will have an edge stretching to the cell n steps away in each direction. The letter-nodes will not have any outgoing edges.

Using this graph, G, try to find a topological ordering. If there are any cycles, no such ordering is possible, and the longest path will be infinite. Use DP to compute the longest path ending in each node. The full algorithm can be read on Longest Path Problem.

void Main()
{
    string text = @"
        75XXX83XXXXX9X06218X
        XX93X7XX4X87XXX611X6
        4XXXX7X5XXXXX3XXX74X
        X5XXX2XXXX5162X7XX97
        X72X1XXXXXXXX2XXX2XX
        9X617X8XX7XXXX1931XX
        X6X14X43XXXXXXXX0166
        7XXX3XXX10XXX30315XX
        X410XXX2XX91X6XX77XX
        X42XXX7XXXXX59X2XXX5
    ";
    int pathLength = FindLongestPathInGrid(text);
    Console.WriteLine(pathLength);
}

int FindLongestPathInGrid(string text)
{
    int pathLength = -1;

    var grid = StringToGrid(text);
    var nodes = GridToNodes(grid);
    var ordering = TopologicalSort(nodes);

    if (ordering != null)
    {
        var longestPath = FindLongestPath(ordering);
        pathLength = longestPath.Count;
    }

    return pathLength;
}

char[,] StringToGrid(string text)
{
    var lines = text.Split('\n')
        .Select(l => l.Trim())
        .Where(l => !string.IsNullOrEmpty(l))
        .ToList();

    var height = lines.Count;
    var width = lines.Max(l => l.Length);

    var grid = new char[height,width];
    for (int y = 0; y < height; y++)
    {
        var line = lines[y];
        for (int x = 0; x < line.Length; x++)
        {
            grid[y, x] = line[x];
        }
    }
    return grid;
}

class Node
{
    public int Index { get; private set; }
    public int Order { get; set; }
    public List<Node> Outgoing { get; private set; }
    public List<Node> Incoming { get; private set; }

    public Node(int index)
    {
        Index = index;
        Order = index;
        Outgoing = new List<Node>();
        Incoming = new List<Node>();
    }

    public void AddOutgoing(Node other)
    {
        Outgoing.Add(other);
        other.Incoming.Add(this);
    }
}

IList<Node> GridToNodes(char[,] grid)
{
    int height = grid.GetLength(0);
    int width = grid.GetLength(1);

    // Create the nodes
    var nodes = new List<Node>();
    for (int y = 0; y < height; y++)
    for (int x = 0; x < width; x++)
    {
        nodes.Add(new Node(y*width + x));
    }

    // Connect them
    for (int y = 0; y < height; y++)
    for (int x = 0; x < width; x++)
    {
        var node = nodes[x+y*width];
        if ('0' <= grid[y,x] && grid[y,x] <= '9')
        {
            int n = grid[y,x] - '0' + 1; // '0'..'9' -> 1..10
            if (x-n >= 0) node.AddOutgoing(nodes[x-n+y*width]);
            if (x+n < width) node.AddOutgoing(nodes[x+n+y*width]);
            if (y-n >= 0) node.AddOutgoing(nodes[x+(y-n)*width]);
            if (y+n < height) node.AddOutgoing(nodes[x+(y+n)*width]);
        }
    }

    return nodes;
}

IList<Node> TopologicalSort(IList<Node> Nodes)
{
    // Compute the in-degree of each node
    var incomingCount = Nodes.Select(n => n.Incoming.Count).ToList();

    int nodeCount = Nodes.Count;

    List<Node> result = new List<Node>();
    while (nodeCount > 0)
    {
        // Find the index of any node with in-degree 0
        var node = Nodes
            .Where((n,i) => incomingCount[i] == 0)
            .FirstOrDefault();

        // None found. No ordering possible.
        if (node == null) return null;

        nodeCount--;

        // Add it to the output
        node.Order = result.Count;
        result.Add(node);

        // Remove it from further consideration
        incomingCount[node.Index] = -1;

        // Decrement the in-degree of any connected nodes.
        foreach (var neighbor in node.Outgoing)
        {
            incomingCount[neighbor.Index]--;
        }
    }

    return result;
}

IList<Node> FindLongestPath(IList<Node> nodeOrdering)
{
    int count = nodeOrdering.Count;
    Node[] cameFrom = new Node[count];
    int[] longestPath = new int[count];

    foreach (var node in nodeOrdering)
    {
        if (node.Incoming.Count > 0)
        {
            Node best = node.Incoming.MaxBy(n => longestPath[n.Order]);
            cameFrom[node.Order] = best;
            longestPath[node.Order] = longestPath[best.Order] + 1;
        }
    }

    var maxLength = longestPath.Max();

    var last = nodeOrdering.MaxBy(n => longestPath[n.Order]);
    return ReconstructPath(cameFrom, last);
}

IList<Node> ReconstructPath(Node[] cameFrom, Node last)
{
    var result = new List<Node>();
    while (last != null)
    {
        result.Add(last);
        last = cameFrom[last.Order];
    }

    result.Reverse();
    return result;
}

public static class Extensions
{
    public static TItem MaxBy<TItem,TKey>(this IEnumerable<TItem> items, Func<TItem,TKey> keySelector)
    {
        var currentBestItem = default(TItem);
        var currentBestKey = default(TKey);
        var comparator = Comparer<TKey>.Default;
        bool hasBest = false;
        foreach (var item in items)
        {
            var key = keySelector(item);
            if (!hasBest || comparator.Compare(key, currentBestKey) > 0)
            {
                currentBestKey = key;
                currentBestItem = item;
                hasBest = true;
            }
        }
        return currentBestItem;
    }
}

Example:

75XXX83XXXXX9X06218X
XX93X7XX4X87XXX611X6
4XXXX7X5XXXXX3XXX74X
X5XXX2XXXX5162X7XX97
X72X1XXXXXXXX2XXX2XX
9X617X8XX7XXXX1931XX
X6X14X43XXXXXXXX0166
7XXX3XXX10XXX30315XX
X410XXX2XX91X6XX77XX
X42XXX7XXXXX59X2XXX5

has a max path-length of 11, and a total of 4 such paths. Here is one:

....................
...3....4......6.1..
....................
...X................ <-- end
....................
...1................
................0... <-- start
.............30.15..
....................
....................
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top