Wyszukiwanie w tablicy dwuwymiarowej

0

Piszę program, który w dowolnie wygenerowanej macierzy, ma wyszukiwać przeszkód. 0 w macierzy to wolna przestrzeń, 1 to przeszkody. Program ma sprawdzić, czy woda płynąca z góry może "przepłynąć" 0 w macierzy. Muszę sprawdzić czy 0 ze sobą sąsiadają w kolejnych wierszach. Zastanawiam się, jak mogę to zrobić. Z góry dziękuję za każdą odpowiedź.

System.out.println("Wprowadż liczbę wierszy");
		Scanner mm = new Scanner(System.in);
		int m = mm.nextInt();
		System.out.println("Wprowadż liczbę kolumn");
		Scanner nn = new Scanner(System.in);
		int n = nn.nextInt();
		Random los = new Random();
		int[][] macierz = new int[m][n];
		for (int w = 0; w < macierz.length; w++) {
			for (int k = 0; k < macierz[w].length; k++) {
				macierz[w][k] = los.nextInt(2);
				System.out.print((macierz[w][k]) + " | ");
			}
			System.out.println();
		}
		int k = 0;
		for (int i = 0; i <= n; i++) {
			if (macierz[k][i] == 0) {
				System.out.println(i);
				break;
			} else {
				continue;
			}
		}
	}
}
0

Jeżeli woda płynie z góry na dół i może przepłynąć tylko w pionie (a nie po skosie, albo na boki), to zadanie jest banalnie proste.

Przykładowa macierz:
0 1 1 0 1
0 0 1 0 0
1 1 1 0 1
0 0 0 0 1

counter = 0

dla każdego elementu w pierwszym wierszu:
    jeżeli element równa się 0:
        dla kazdego elementu o tym samym indeksie w pozostalych wierszach:
              jezeli element rowna sie 0:
                    counter++;
        jezeli counter jest równy liczbie wierszy + 1
              zwróć true

zwroc false

Zdaje sobie sprawę, że nie jest to najbardziej optymalny sposób, ale z grubsza działa ;)

0

Niestety woda może płynąć na boki i w dół

0

Jest w tym zadaniu jakiś priorytet kierunku? Chodzi mi o to, czy jeśli mamy coś takiego:

0  0
0  0

i zaczynamy z lewego górnego wierzchołka, to w którym kierunku najpierw powinna płynąć ta woda?

0

Wrzucasz sobie tę macierz w formie jak jest, wprowadzasz dodatkowy stan (niech będzie 2 - zalany). Zaczynasz "polewać" całość cyfrową wodą:

  • Zmieniasz wszystkie 0 z pierwszego wiersza na 2
    Dla każdego następnego wiersza wykonujesz następującą sekwencję:
    loop:
    Dla każdego 0 sprawdzasz czy w pole [m, n-1] == 2, jeżeli tak - ustawiasz je również na 2
    ustawiasz sąsiadujące ([m-1, n], [m+1, n]) pola na 2, powtarzasz krok rekurencyjnie dla nowych "2"
0

Jest sobie Algorytm Djikstry, który służy do rozwiązywania tego typu problemów. U ciebie jedynym problemem jest przerobienie tablicy na graf, który będzie można wykorzystać jako pokarm dla Edsgera :D

Jak to zrobić?

Zacznij z lewego górnego rogu i szukaj wierszami zer. Trafiasz na zero, to sprawdzasz czy sąsiedzi z prawej, lewej i z dołu to zera, jak tak to tworzysz połączenie, jak nie to nie.

1 użytkowników online, w tym zalogowanych: 0, gości: 1