Dan Dan - 3 months ago 29
C# Question

Print all possible paths in a labyrinth using recursive DFS

This is the task: You are given a labyrinth, which consists of N x N squares, each of it can be passable or not. Passable cells consist of lower Latin letter between "a" and "z", and the non-passable – '#'. In one of the squares is Jack. It is marked with "*".

Two squares are neighbors, if they have common wall. At one step Jack can pass from one passable square to its neighboring passable square. When Jack passes through passable squares, he writes down the letters from each square. At each exit he gets a word. Write a program, which from a given labyrinth prints the words, which Jack gets from all the possible exits.
The input data is read from a text file named Labyrinth.in. At the first line in the file there is the number N (2 < N < 10). At each of the next N lines there are N characters, each of them is either Latin letter between "a" and "z" or "#" (impassable wall) or "*" (Jack). The output must be printed in the file Labyrinth.out.

Input:

6
a##km#
z#ada#
a*m###
#d####
rifid#
#d#d#t


So far I've done that :

using System;
using System.IO;
using System.Collections.Generic;
using System.Text;

public class Maze
{
private const string InputFileName = "Labyrinth.in";
private const string OutputFileName = "Labyrinth.out";
StringBuilder path = new StringBuilder();

public class Cell
{
public int Row { get; set; }
public int Column { get; set; }

public Cell(int row, int column)
{
this.Row = row;
this.Column = column;
}
}

private char[,] maze;
private int size;
private Cell startCell = null;

public void ReadFromFile(string fileName)
{
using (StreamReader reader = new StreamReader(fileName))
{
// Read maze size and create maze
this.size = int.Parse(reader.ReadLine());
this.maze = new char[this.size, this.size];

// Read the maze cells from the file
for (int row = 0; row < this.size; row++)
{
string line = reader.ReadLine();
for (int col = 0; col < this.size; col++)
{
this.maze[row, col] = line[col];
if (line[col] == '*')
{
this.startCell = new Cell(row, col);
}
}
}
}
}

public void FindAllPathsAndPrintThem()
{
if (this.startCell == null)
{
// Start cell is missing -> no path
SaveResult(OutputFileName, "");
return;
}

VisitCell(this.startCell.Row,
this.startCell.Column, path);

if (path.Length == 0)
{
// We didn't reach any cell at the maze border -> no path
SaveResult(OutputFileName, "");
return;
}
}

private void VisitCell(int row, int column, StringBuilder path)
{
if (row < 0 || row > maze.GetLength(0) - 1 ||
column < 0 || column > maze.GetLength(1) - 1)
{
SaveResult(OutputFileName, path.ToString());
return;
}

if (this.maze[row, column] != 'x' && this.maze[row, column] != '#')
{
// The cell is free --> visit it
if (this.maze[row, column] != '*')
{
path.Append(this.maze[row, column]);
this.maze[row, column] = 'x';
}
VisitCell(row, column + 1, path);
VisitCell(row, column - 1, path);
VisitCell(row + 1, column, path);
VisitCell(row - 1, column, path);
}
}

public void SaveResult(string fileName, string result)
{
using (StreamWriter writer = new StreamWriter(fileName))
{
writer.WriteLine(result);
}
}

static void Main()
{
Maze maze = new Maze();
maze.ReadFromFile(InputFileName);
maze.FindAllPathsAndPrintThem();
}
}


Sorry for long question. There need to be a small bug but I don't get it where.
The output is madifiddrdzaadamk. Thanks in advance.

Answer

Here's a solution I came up with. It keeps track of what cells have been visited during one go through the maze, but not for all attempts. This can be done by making the function return an IEnumerable<string> that will represent the paths to an exit from the current point in the maze. First check if you have gone off the edge of the maze and return nothing. Then check if you're at a wall and if so no path is returned. Otherwise you check if you are at the edge and if so you return the path that is represented by the current cell only. Then you have to mark the current cell as visited, then attempt to find all paths in each of the 4 directions and concatenate the current cell to any that you find and yield them. Then at the end you mark the cell as not visited so it can be used for other attempts.

private static IEnumerable<string> VisitCell(int row, int column, bool[,] visited)
{
    if (row < 0 || column < 0 || row >= maze.GetLength(0) || column >= maze.GetLength(1))
        yield break;

    if (maze[row, column] == '#' || visited[row, column])
        yield break;

    if (row == 0 || row == maze.GetLength(0) - 1 ||
        column == 0 || column == maze.GetLength(1) - 1)
    {
        yield return maze[row, column].ToString();
    }

    visited[row, column] = true;

    foreach (var path in VisitCell(row, column + 1, visited))
    {
        yield return maze[row, column] + path;
    }

    foreach(var path in VisitCell(row, column - 1, visited))
    {
        yield return maze[row, column] + path;
    }

    foreach (var path in VisitCell(row + 1, column, visited))
    {
        yield return maze[row, column] + path;
    }

    foreach (var path in VisitCell(row - 1, column, visited))
    {
        yield return maze[row, column] + path;
    }

    visited[row, column] = false;
}

Then you can run this code

private static char[,] maze =
{
    { 'a', '#', '#', 'k', 'm', '#' },
    { 'z', '#', 'a', 'd', 'a', '#' },
    { 'a', '*', 'm', '#', '#', '#' },
    { '#', 'd', '#', '#', '#', '#' },
    { 'r', 'i', 'f', 'i', 'd', '#' },
    { '#', 'd', '#', 'd', '#', 't' }
};

private static void Main(string[] args)
{
    foreach(var path in VisitCell(2, 1, new bool[6, 6]))
        Console.WriteLine(path);
}

to get this result

*madam

*madamk

*madk

*madkm

*a

*az

*aza

*difid

*dir

*did

You can tweak it to remove the star from the beginning of each path.

Comments