KilJaeden написав:Моє завдяння знайти кількість груп однаковіх чисел які записані у двовимірний масив двома способами використовуючи Рекурсивний пошук в глибину і не рекурсивний пошук в ширину (на мові java). Як це зробити? Або з чого слід почати?
|000000000000001100000000|
|000111000000111110000000|
|000111000011111111100000|
|000111001111111111111000|
|000000000000000000000000|
|110000000011111111000000|
|111000000011000111000000|
|111100000011111111000000|
|000000000000000000000000|
наприклад відповідь на цю матрицю 4
Така задача була розв'язана тут на C.
Тільки там (в рядку 81)
getAreasCount(field, 0)
був пошук нулів. А вам потрібно буде шукати одиниці.
Приклад на Java :
import java.util.Arrays;
public class RecursiveSearchExample {
public static void main(String []args) {
// Init 2d array
final String[] inputStr = new String[] {
"000000000000001100000000",
"000111000000111110000000",
"000111000011111111100000",
"000111001111111111111000",
"000000000000000000000000",
"110000000011111111000000",
"111000000011000111000000",
"111100000011111111000000",
"000000000000000000000000"
};
// Convert 2d array
final boolean[][] boolArray = getBool2dArray(inputStr);
// Find areas count
System.out.println("count = " + getAreasCount(boolArray) + "\r\n");
// Print 2d array
print2dArray(boolArray);
}
public static boolean[][] getBool2dArray(final String[] strArr) {
final boolean[][] arr = new boolean[strArr.length][];
for(int i = 0; i < strArr.length; ++i) {
arr[i] = new boolean[strArr[i].length()];
for(int c = 0; c < strArr[i].length(); ++c)
arr[i][c] = strArr[i].charAt(c) == '1';
}
return arr;
}
public static void print2dArray(final boolean[][] arr) {
for(int i = 0; i < arr.length; ++i) {
for(int c = 0; c < arr[i].length; ++c)
System.out.print(arr[i][c] ? '1' : '0');
System.out.println();
}
}
public static boolean[][] getCopy(final boolean[][] arr) {
if(arr == null) return null;
final boolean[][] copy = new boolean[arr.length][];
for(int i = 0; i < arr.length; ++i)
copy[i] = (arr[i] == null ? null : Arrays.copyOf(arr[i], arr[i].length));
return copy;
}
public static int getAreasCount(final boolean[][] arr) {
int count = 0;
final boolean[][] copy = getCopy(arr);
for(int row_i = 0; row_i < copy.length; ++row_i) {
if(copy[row_i] == null) continue;
for(int col_i = 0; col_i < copy[row_i].length; ++col_i) {
if(copy[row_i][col_i]) {
recursiveFunction(copy, col_i, row_i);
++count;
}
}
}
return count;
}
public static void recursiveFunction(final boolean[][] arr, final int x, final int y) {
if(y < 0 || y >= arr.length) return;
if(x < 0 || x >= arr[y].length) return;
if(!arr[y][x]) return;
arr[y][x] = false;
recursiveFunction(arr, x + 1, y);
recursiveFunction(arr, x, y - 1);
recursiveFunction(arr, x - 1, y);
recursiveFunction(arr, x, y + 1);
}
}
