[C#] Nationwide Competition - Kassiopeia [Part 2]

Hey Mates,
it’s weekend and I’ve got some time, so here is my second part.
Little Note: It’s damn hot :sunglasses:, but I hope my text is understandable


Description

Kassiopeia can only walk about white fields on the board. The exercise is to calculate whether she can reach all fields or not. A board looks like this:
http://www.bundeswettbewerb-informatik.de/uploads/media/kassiopeia2.txt
The "#"s are black fields, so Kassiopeia can’t walk about them and the spaces are white fields. The “K” shows where Kassiopeia starts. She can only walk north, east, south or west per step. Diagonal is not allowed!
In this example Kassiopeia can reach all fields.

Example boards

You can get a folder with all examples here.
Can Kassiopeia reach all fields?
0) Yes

  1. No
  2. Yes
  3. Yes
  4. Yes
  5. Yes
  6. Yes
  7. Yes

My Solution

My solution is to find Kassiopeias position as starting point and then use a recursive algorithm to append all fields, that can be reached by her, to a list. After that I compare the length of this to the count of all white fields.

The source:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

using System.IO;

//You want to know what recursion is? Have a look at line 190!

namespace Kassiopeia
{
    class Program
    {
        static void Main(string[] args)
        {
            int rows = 0;
            int columns = 0;

            while (true)
            {
                //Get file
                String file = input("\nText File: ");

                //Read file / Fill board
                StreamReader f = new StreamReader(file);
                Char[,] board = null;
                String line;
                int counter = 0;
                while((line = f.ReadLine()) != null)
                {
                    //First line -> Read rows and columns / Create board
                    if (counter == 0)
                    {
                        rows = int.Parse(line.Split(' ')[0]);
                        columns = int.Parse(line.Split(' ')[1]);

                        board = new Char[rows, columns];
                    }

                    //Else -> Fill board
                    else
                    {
                        for (int i = 0; i < columns; i++)
                        {
                            board[counter - 1, i] = line[i];
                        }
                    }

                    counter += 1;
                }

                // Test if every field is connected
                if (testBoard(board, rows, columns))
                {
                    Console.WriteLine("[*] Kassiopeia can reach all fields!");
                }

                else
                {
                    Console.WriteLine("[!] Kassiopeia can't reach all fields!");
                }
            }
        }

        static bool testBoard(Char[,] board, int rows, int cols)
        {
            //Find Kassiopeias position as starting point / Run recursive test to find all connected fields
            int lenConnected = 0;
            for (int row = 0; row < rows; row++)
            {
                for (int col = 0; col < cols; col++)
                {
                    if (board[row, col] == 'K')
                    {
                        List<String> connected = new List<String>();
                        lenConnected = recursiveTestOfDoom(board, connected, row, col, rows, cols).Count;
                    }
                }
            }

            //Count all white fields
            int lenAll = 0;
            for (int row = 0; row < rows; row++)
            {
                for (int col = 0; col < cols; col++)
                {
                    if (board[row, col] == ' ')
                    {
                        lenAll += 1;
                    }
                }
            }

            //Test if all can be reached
            if (lenConnected < lenAll)
            {
                return false;
            }

            return true;
        }

        /// <summary>
        /// A recursive test of Doooooooom
        /// </summary>
        /// <param name="board"></param>
        /// <param name="connected"></param>
        /// <param name="row"></param>
        /// <param name="col"></param>
        /// <param name="rows"></param>
        /// <param name="cols"></param>
        /// <returns></returns>
        static List<String> recursiveTestOfDoom(Char[,] board, List<String> connected, int row, int col, int rows, int cols)
        {
            //Test above field
            if (row != 0)
            {
                if (board[row - 1, col] == ' ')
                {
                    if (!connected.Contains(toXyString(row - 1, col)))
                    {
                        connected.Add(toXyString(row - 1, col));
                        connected = recursiveTestOfDoom(board, connected, row - 1, col, rows, cols);
                    }
                }
            }

            //Test right field
            if (col != cols - 1)
            {
                if (board[row, col + 1] == ' ')
                {
                    if (!connected.Contains(toXyString(row, col + 1)))
                    {
                        connected.Add(toXyString(row, col + 1));
                        connected = recursiveTestOfDoom(board, connected, row, col + 1, rows, cols);
                    }
                }
            }

            //Test below field
            if (row != rows - 1)
            {
                if (board[row + 1, col] == ' ')
                {
                    if (!connected.Contains(toXyString(row + 1, col)))
                    {
                        connected.Add(toXyString(row + 1, col));
                        connected = recursiveTestOfDoom(board, connected, row + 1, col, rows, cols);
                    }
                }
            }

            //Test left field
            if (col != 0)
            {
                if (board[row, col - 1] == ' ')
                {
                    if (!connected.Contains(toXyString(row, col - 1)))
                    {
                        connected.Add(toXyString(row, col - 1));
                        connected = recursiveTestOfDoom(board, connected, row, col - 1, rows, cols);
                    }
                }
            }

            return connected;
        }

        /// <summary>
        /// Builds a little String out of the x and y coordinate
        /// </summary>
        /// <param name="row"></param>
        /// <param name="col"></param>
        /// <returns></returns>
        static String toXyString(int row, int col)
        {
            return row.ToString() + col.ToString();
        }

        static String input(String text)
        {
            Console.Write(text);
            return Console.ReadLine();
        }
    }
}

//You want to know what recursion is? Have a look at line 9!

Conclusion

This is a very good challenge for learning some fundamentals like reading text files, twodimensional arrays and maybe recursion (Depends on your solution). Have fun while learning! (Yes that sounds like a lame slogan from a latin teacher :grin:)

|-TheDoctor-|

1 Like

This topic was automatically closed after 30 days. New replies are no longer allowed.