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:
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
- No
- Yes
- Yes
- Yes
- Yes
- Yes
- 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 
)
|-TheDoctor-|