-
Notifications
You must be signed in to change notification settings - Fork 17
/
CountSeaShips.java
49 lines (45 loc) · 2.43 KB
/
CountSeaShips.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package by.andd3dfx.search;
/**
* Есть матрица NxN, состоящая из 0 и 1, и отражающая расположение кораблей на поле для морского боя.
* Поле может быть любого размера, но обязательно квадратное.
* Кораблей может быть любое кол-во.
* Размер кораблей - от 1х1 до 1хN
* Корабли никак не соприкасаются друг с другом.
* Необходимо подсчитать кол-во кораблей.
*
* @see <a href="https://youtu.be/9ypQAA7ilYo">Video solution</a>
*/
public class CountSeaShips {
/**
* Использовал идеи из
* https://medium.com/unilecs/%D0%BC%D0%BE%D1%80%D1%81%D0%BA%D0%BE%D0%B9-%D0%B1%D0%BE%D0%B9-9109dafcbc5
* <p>
* Если на очередном шаге мы встретили клетку корабля, проверяем предыдущую клетку по вертикали и по горизонтали,
* если там также находится клетка корабля, то пропускаем эту итерацию, т.к. уже посчитали этот корабль раньше.
* <p>
* Если же на очередном шаге мы встретили клетку корабля и предыдущие клетки по горизонтали и вертикали не являются
* клетками корабля, то значит мы нашли 1ю клетку нового корабля. В этом случае увеличиваем наш результирующий
* счетчик.
*/
public static int count(int[][] matrix) {
var size = matrix.length;
var result = 0;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (matrix[i][j] == 1) {
boolean isNewShip = checkIsNewShip(matrix, i, j);
if (isNewShip) {
result++;
}
}
}
}
return result;
}
private static boolean checkIsNewShip(int[][] matrix, int i, int j) {
if ((i > 0 && matrix[i - 1][j] == 1) || (j > 0 && matrix[i][j - 1] == 1)) {
return false;
}
return true;
}
}