Подсчет кол-ва кораблей на поле морского боя - C#
Формулировка задачи:
Имеется задача:
Подсчитать кол-во кораблей каждого типа на поле из файла input. Где первая строка - размер поля (NxN), "#" - часть корабля, а "." - пустая клетка. В output надо вывести результат (<вид_корабля>.<кол-во>). Дошел до момента, когда у меня есть список верных точек. Как из этого сгруппировать их в корабли? Или мб есть еще более простой и быстрый способ решения? Хранятся координаты в листе массивов ([0] = x, [1] = y);
Все, что нарешал.
input:
10 ....###..# .........# ###......# .....#...# #..#...... #..#.....# .......... #......... .......... ......#...
static void Main(string[] args)
{
StreamReader sr = new StreamReader("input.txt");
int count = Int32.Parse(sr.ReadLine()),
num = 0;
char[,] data = new char[count, count];
List<int[]> ships = new List<int[]>();
bool exit = false;
while (!sr.EndOfStream && exit == false)
{
string line = sr.ReadLine();
for (int i = 0; i < count; i++)
{
data[num, i] = line[i];
if (data[num, i] == '#')
{
int[] cur_ship = new int[] { num, i };
if (ships.Count > 1)
{
for (int k = 0; k < ships.Count; k++)
{
if (Corrected(ships[ships.Count - 1], ships[k]) == false)
{
exit = true;
}
}
}
ships.Add(cur_ship);
Console.WriteLine("Ship founded");
Console.WriteLine("x={0}, y={1}", num.ToString(), i.ToString());
}
}
num++;
if (num > count) break;
}
if (exit) Console.WriteLine("INPUT_ERROR");
else {
for (int i = 0; i < ships.Count; i++)
{
for (int j = i+1; j < ships.Count; j++)
{
if ((ships[i][0] == ships[j][0] && Math.Abs(ships[i][1] - ships[j][1]) == 1) ||
(ships[i][1] == ships[j][1] && Math.Abs(ships[i][0] - ships[j][0]) == 1))
{
Console.WriteLine("From x={0};y={1} to x={2};y={3}", ships[i][0], ships[i][1], ships[j][0], ships[j][1]);
}
}
}
}
Console.ReadLine();
}
static bool Corrected(int[] part1, int[] part2)
{
int x1 = part1[0],
y1 = part1[1],
x2 = part2[0],
y2 = part2[1];
if (((x1 == x2 - 1) && //
((y1 == y2 - 1) || // [x1-1,y1-1] [x1+1,y1-1]
(y1 == y2 + 1))) || // [x1,y1]
((x1 == x2 + 1) && // [x1-1,y1+1] [x1+1,y1+1]
((y1 == y2 - 1) || //
(y1 == y2 + 1))))
{
return false;
}
else
{
return true;
}
}Решение задачи: «Подсчет кол-ва кораблей на поле морского боя»
textual
Листинг программы
public class BattleField
{
private bool[][] _battleField;
public BattleField(bool[][] battleField)
{
_battleField = battleField;
}
public IDictionary<int, int> GetShipCount()
{
var result = new Dictionary<int, int>();
for (var i = 0; i < _battleField.Length; i++)
{
for (var j = 0; j < _battleField[i].Length; j++)
if (_battleField[i][j])
{
var count = GetShipSize(i, j);
if (!result.ContainsKey(count)) result[count] = 0;
result[count]++;
}
}
return result;
}
public int GetShipSize(int i, int j)
{
var result = _battleField[i][j] ? 1 : 0;
_battleField[i][j] = false;
if (j < _battleField[i].Length - 1 && i < _battleField.Length - 1 && _battleField[i + 1][j + 1]
&& !_battleField[i][j + 1] && !_battleField[i + 1][j])
throw new Exception("invalid input "+(i+1)+" "+(j+1));
if (j > 0 && i < _battleField.Length-1 && !_battleField[i][j-1] && !_battleField[i+1][j] && _battleField[i+1][j-1])
throw new Exception("invalid input "+(i+1)+" "+(j-1));
if (j < _battleField[i].Length-1 && _battleField[i][j + 1])
{
result += GetShipSize(i, j + 1);
}
if (i < _battleField.Length-1 && _battleField[i + 1][j])
{
result += GetShipSize(i + 1, j);
}
if (j > 0 && _battleField[i][j - 1])
{
result += GetShipSize(i, j - 1);
}
return result;
}
}