1

Тема: Рекурсивний пошук в глибину і не рекурсивний пошук в ширину

Моє завдяння знайти кількість груп однаковіх чисел які записані у двовимірний масив двома способами використовуючи Рекурсивний пошук в глибину і не рекурсивний пошук в ширину (на мові java). Як це зробити? Або з чого слід почати?

|000000000000001100000000|
|000111000000111110000000|
|000111000011111111100000|
|000111001111111111111000|
|000000000000000000000000|
|110000000011111111000000|
|111000000011000111000000|
|111100000011111111000000|
|000000000000000000000000|

наприклад відповідь на цю матрицю 4

2

Re: Рекурсивний пошук в глибину і не рекурсивний пошук в ширину

Статтю на Вікі вже прочитали?

3

Re: Рекурсивний пошук в глибину і не рекурсивний пошук в ширину

Так але не дуже зрозумів як знайти окремі конструкції. На одновимірному масиві я впораюсь а од з двовимірним у мене складнощі. Булоб добре побачити приклад розв'язання подібної задачі.

4

Re: Рекурсивний пошук в глибину і не рекурсивний пошук в ширину

А до чого тут масив і його вимірність? У вас є граф. Все, що вам треба - якось запам'ятовувати вершини (тобто, у даному випадку - дві координати) і знаходити сусідні вершини (додаванням ±1 до координат). У чому саме проблема?

Подякували: KilJaeden1

5

Re: Рекурсивний пошук в глибину і не рекурсивний пошук в ширину

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);
    }
}
Подякували: KilJaeden1