 # [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 , 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:
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

[Spoiler]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.[/Spoiler]

The source:

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

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: ");

Char[,] board = null;
String line;
int counter = 0;
{
//First line -> Read rows and columns / Create board
if (counter == 0)
{
rows = int.Parse(line.Split(' '));
columns = int.Parse(line.Split(' '));

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 = 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 = 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 = 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 = 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);
}
}
}

//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 )

|-TheDoctor-|

1 Like

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