Zadanie na tablicy 2-wymiarowej

Cześć, mam za zadanie napisać funkcję, która modyfikowałaby tablicę 2 wymiarową, która jest wypełniona intami o wartościach od 0 do 9. Modyfikacja polagałaby na tym że, do funkcji zostaje przekazana współrzędna liczby we wspomnianej tablicy i w zależności od tego jaka wartość ma wskazana liczba:
0 - nic się nie dzieje
1 - liczba zmienia wartość na 0
każda inna cyfra powoduje wyzerowanie wszystkich liczb które leżą pod nią, nad nią, na lewo i na prawo. Zasięg jest zależny od tego jaką wartość ma dana liczba. Przykładowo cyfra 3 ma następujący zasięg:
. . X . .
. . X . .
XX3XX
. . X . .
. . X . .

Dodatkowo zerowane liczby również mogą zerować kolejne tak jak w przykładzie z liczbą 3 co prowadzi do powstania reakcji łańcuchowej. Próbowałem szukać podobnych problemów, implementacji itd ale bez powodzenia. Help

Pokaż co już zrobiłeś!
W tej chwili wygląda to na "zróbcie za mnie zadanie domowe".

"Próbowałem szukać podobnych problemów, implementacji itd ale bez powodzenia" - Pokaż co Próbowałeś, żebyśmy nie powtarzali złych rozwiązań.

Jest to część większej całości :) próbowałem iteracyjnie przechodzić najpierw po wierszach później po kolumnach w zasięgu danej liczby i dodawać lokalizacje liczb "do wyzerowania" do tymczasowej tablicy i na koniec po prostu pętla wyzerowac liczby ze zgromadzonych lokalizacji. Problem był w tym, że nie do końca umiałem to zaimplementowac bo robiło się to bardzo skomplikowane i dodatkowo w takim rozwiązaniu gromadzilem duplikaty lokalizacji.

Dodatkowo zerowane liczby również mogą zerować kolejne tak jak w przykładzie z liczbą 3 co prowadzi do powstania reakcji łańcuchowe.

Objasnij to, kiedy następuje ta "reakcja łańcuchowa", gdy zerując natrafiamy na liczby 2 - 9?

Dokładnie tak, kiedy zerując natrafimy na liczbę od 2 do 9 to każda z nich powoduje kolejne zerowania

Próbowałeś może najprostszego breadth/depth first search?

Spróbuj sobie zrobić to zadanie na rozgrzewkę
https://leetcode.com/problems/number-of-islands/

Próbowałeś może najprostszego breadth/depth first search?

Trawersowanie grafu? to jak z armaty do muchy)

próbowałem iteracyjnie przechodzić najpierw po wierszach później po kolumnach w zasięgu danej liczby i dodawać lokalizacje liczb "do wyzerowania" do tymczasowej tablicy i na koniec po prostu >
pętla wyzerowac liczby ze zgromadzonych lokalizacji.

Dziwne, bo tak właśnie można to rozwiązać, funkcja z zeruje wiersz i kolumnę o danych współrzędnych, struktura Coordinates przechowuje współrzędne do wyzerowania:

class Main {
  static class Coordinates {
    public int a, b;
  }
  static int [][] z(int [][] arr, int sz, int x, int y) {
    for (int i = 0; i < sz; i++)
      arr[x][i] = 0;
    for (int i = 0; i < sz; i++)
      arr[i][y] = 0;
    return arr;
  }
  static int [][] zeroArray(int [][] arr, int sz, int x, int y) {
    if (0 == arr[x][y]) return arr;
    else if (1 == arr[x][y]) {arr[x][y] = 0; return arr;}
    else{
        Coordinates [] c = new Coordinates[sz * sz];
        for (int i = 0; i < sz * sz; ++i)
           c[i] = new Coordinates();
        int cnt = 0;
        for (int i = 0; i < sz; i++) {
          if (1 < arr[x][i]){
            c[cnt].a = x;
            c[cnt].b = i;
            ++cnt;
          }
        }
        for (int i = 0; i < sz; i++) {
          if (1 < arr[i][y]){
            c[cnt].a = i;
            c[cnt].b = y;
            ++cnt;
          }
        }
        for (int i = 0; i < cnt; ++i)
          arr = z(arr, sz, c[i].a, c[i].b);
        return arr;
    }
  }
  static void printArray(int [][] arr, int sz){
    for (int i = 0; i < sz; i++) {
      for (int j = 0; j < sz; j++){
        System.out.print(arr[i][j]);
        System.out.print(" ");
      }
      System.out.println();
    }
  }
  public static void main(String[] args) {
    int n = 4;
    int [][] a = new int[n][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++){
        a[i][j] = 1;
      }
    }
    a[1][1] = 2;
    a[1][3] = 2;
    printArray(a, n);
    a = zeroArray(a, 4, 1, 1);
    System.out.println(" ");
    printArray(a, n);
  }
}

@lion137 Nie do końca o to chodziło. Problem w tym, że nie uwzględniłeś zasięgu zerowania. Np liczba 2 zeruje po 1 dodatkowej liczbie na lewo, na prawo, nad sobą i pod sobą (liczba 3 zeruje 2, 4 - 3 itd):

. . X . .
. X2X .
. . X . .

Gdzie "X" oznacza zerowaną liczbę. I dodatkowo liczby oznaczone jako X powodują kolejne zerowania w taki sam sposób co tworzy reakcję łańcuchową. Twoja funkcja "z" kasuje cały wiersz i kolumnę bez uwzględnienia zasięgu.

Przykładowo tablica:
1 1 1 1
1 2 2 1
1 1 2 1
1 1 1 1

Liczba, od której zaczynamy zerowanie ma współrzędne (1,1) i wartość 2. Poprawny wynik to taka tablica:

1 0 0 1
0 0 0 0
1 0 0 0
1 1 0 1

Wynik Twojej funkcji:

1 0 0 1
0 0 0 0
1 0 0 1
1 0 0 1

Trzeba było to wyłożyć w pierwszym poście.

Może zbyt myląco to opisałem... sorki.

każda inna cyfra powoduje wyzerowanie wszystkich liczb które leżą pod nią, nad nią, na lewo i na prawo. Zasięg jest zależny od tego jaką wartość ma dana liczba. Przykładowo cyfra 3 ma następujący zasięg:
. . X . .
. . X . .
XX3XX
. . X . .
. . X . .

Dodatkowo zerowane liczby również mogą zerować kolejne tak jak w przykładzie z liczbą 3 co prowadzi do powstania reakcji łańcuchowej. Próbowałem szukać podobnych problemów, implementacji itd ale bez powodzenia. Help

Cool, wydaje mi się, że można uratować to rozwiązanie, przerabiając, funkcję z i funkcję główna też.

Czy zna ktoś podobne problemy? Chodzi mi głównie o implementację tej "reakcji łańcuchowej"

Szczerze mówiąc, zupełnie nie rozumiem z czym masz problemy.
Z napisaniem 15-20 wierszowej funkcji?

Tak, mam problem z tą funkcją, inaczej nie zakładałbym tego wątku

@InterruptedException: miał rację (chociaż, ja myślałem o innym problemie), należy to zrobić jako trawersowanie grafu:
lista sąsiedztwa to będą punkty w "zasięgu" liczb większych od jeden;
wierzchołki to punkty tablicy;
a "zamarkowanie" wierzchołka to wyzerowanie.
A jaką się tam strukturę podepnie, stack - dfs, FIFO - bfs, to nie powinno mieć znaczenia.

class Table
{
   private static final int[][] IncXY=new int[][] {{0,-1},{0,+1},{-1,0},{+1,0}};
   private final int[][] map;
   public Table(int[][] map) { this.map=map; }
   public boolean OutRange(int x,int y) { return (0>y||y>=map.length||0>x||x>=map[y].length); }
   public void proceed(int x,int y)
   {
      if(OutRange(x,y)) return;
      int value=map[y][x];
      map[y][x]=0;
      for(int[] inc:IncXY)
      {
         int dx=inc[0],dy=inc[1],cx=x,cy=y;
         for(int i=1;(i<value)&&(!OutRange(cx+=dx,cy+=dy));++i) map[cy][cx]=0;
      }
   }
}

Poprawiono zgodnie z zeznaniem: Zadanie na tablicy 2-wymiarowej

Niestety powyższy program nie spełnia warunków zadania:
Powinien pobierać tylko współrzędne punktu w tablicy (ewentualnie tablicę), a ma jeszcze dodatkowy parametr value(?);
Daje błędne wyniki, np, dla tablicy:

1 1 1 1
1 3 1 3
1 1 1 1
1 1 1 1

I podanych współrzędnych (1, 1) czyli ta trójka z lewej, powininno być:

    1 0 1 0
    0 0 0 0
    1 0 1 0
    1 0 1 0

A jest:

1 0 1 1
0 3 0 0
1 0 1 1
1 0 1 1

Dodatkowo podanie innego value zmienia działanie programu, co świadczy o niezrozumieniu polecenia, gdyż modyfikacja ma zależeć tylko od współrzędnych i wartości w tablicy dla podanych [współrzędnych].

@lion137, przeczytaj zadanie ze zrozumieniem, proszę. Nawet przykład podano!
Zeznanie autora tematu: Zadanie na tablicy 2-wymiarowej

Przykład z: Zadanie na tablicy 2-wymiarowej
Twoje rozwiązanie (zmieniłem na map[y][x] = 0:
https://repl.it/@lion137/zeroArray2

Dla tablicy wejściowej:

1 1 1 1
1 3 1 3
1 1 1 1
1 1 1 1

I rozpoczęciu od liczby o lokalizacji (1,1), która ma wartość 3 poprawna tablica na wyjściu powinna wyglądać tak:

1 0 1 0
0 0 0 0
1 0 1 0
1 0 1 0

Tak jak napisał @lion137

Rozwiązanie na bazie dfs, choć kod nie wygląda przepięknie:), konceptualnie jest dla mnie ładne.

import java.util.*;
class Array {
  private int [][] arr;
  private int sz;
  private HashSet <ArrayList<Integer>> marked = new HashSet<>();
  public Array (int [][] a) {
    this.arr = a;
    this.sz = arr.length;
  }
  
  public  List<ArrayList<Integer>> adj(ArrayList<Integer> c) {
    int x = c.get(0);
    int y = c.get(1);
    int val = arr[x][y];
    int row_left = Math.max(x - (val - 1), 0);
    int row_right = Math.min(x + (val - 1), sz - 1);
    int col_up = Math.max(y - (val - 1), 0);
    int col_down = Math.min(y + (val - 1), sz - 1);
    List<ArrayList<Integer>> lst = new ArrayList<>();
    for (int i = row_left; i <= row_right; ++i) {
      if (i != x){

        lst.add(new ArrayList<>(Arrays.asList(i, y)));
      }
    }
    for (int i = col_up; i <= col_down; ++i) {
      if (i != y) {
        lst.add(new ArrayList<>(Arrays.asList(x, i)));
      }
    }
    return lst;
  }

 public void traverseArray(int x, int y) {
    List <ArrayList<Integer>> s = new ArrayList<>();
    ArrayList<Integer> tile = new ArrayList<>(Arrays.asList(x, y));
    s.add(tile);
    while (! s.isEmpty()) {
      tile = s.remove(s.size() - 1);
      if ( ! this.marked.contains(tile)) {
        this.marked.add(tile);
        for (ArrayList<Integer> v: adj(tile)) {
          s.add(v);
        }
      }
    }
    for (ArrayList<Integer> e : marked){
      arr[e.get(0)][e.get(1)] = 0;
    }
  }

  public void changeArray(int x, int y){
    if (arr[x][y] == 0)
      return;
    if (arr[x][y] == 1) {
      arr[x][y] = 0;
      return;
    }
    traverseArray(x, y);
  }

  //print
  public void printArray(){
    for (int i = 0; i < sz; i++) {
      for (int j = 0; j < sz; j++){
        System.out.print(arr[i][j]);
        System.out.print(" ");
      }
      System.out.println();
    }
  }
}

class Main {
    public static void main(String[] args) {
    int n = 4;
    int [][] a = new int[n][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++){
        a[i][j] = 1;
      }
    }
    a[1][1] = 2;
    a[1][2] = 2;
    a[2][2] = 2;

    Array ar = new Array(a);
    ar.printArray();
    System.out.println();
    ar.changeArray(1, 1);
    ar.printArray();
    ar.changeArray(0, 0);
    System.out.println();
    ar.printArray();
    }
}

EDIT: Zamiana stosu z LinkedList na ArrayList (linia 35), poprawia nieco wydajność czasową i pamięciową.

Chyba zaczyna mi się Łysienie
A i tak wystarczy jedną operację zastąpić:

class Table
{
   private static final int[][] IncXY=new int[][] {{0,-1},{0,+1},{-1,0},{+1,0}};
   private final int[][] map;
   public Table(int[][] map) { this.map=map; }
   public boolean OutRange(int x,int y) { return (0>y||y>=map.length||0>x||x>=map[y].length); }
   public void proceed(int x,int y)
   {
      if(OutRange(x,y)) return;
      int value=map[y][x];
      map[y][x]=0;
      for(int[] inc:IncXY)
      {
         int dx=inc[0],dy=inc[1],cx=x,cy=y;
         for(int i=1;(i<value)&&(!OutRange(cx+=dx,cy+=dy));++i) proceed(cx,cy);
      }
   }
}

class Table
{
   private static class Cell
   {
      public int x,y;
      public Cell(int x,int y) { this.x=x; this.y=y; }
   }
   private static final Cell[] IncXY=new Cell[]
   {
      new Cell(0,-1),new Cell(0,+1),new Cell(-1,0),new Cell(+1,0)
   };
   private final HashSet<Cell> queue=new HashSet<>();
   private final int[][] map;
   public Table(int[][] map) { this.map=map; }
   public boolean OutRange(int x,int y) { return (0>y||y>=map.length||0>x||x>=map[y].length); }
   public void proceed(int x,int y)
   {
      queue.clear();
      if(OutRange(x,y)) return;
      queue.add(new Cell(x,y));
      proceed();
   }
   public void proceed()
   {
      while(!queue.isEmpty())
      {
         Cell pt=queue.iterator().next();
         queue.remove(pt);
         int x=pt.x,y=pt.y;
         int value=map[y][x];
         map[y][x]=0;
         for(Cell inc:IncXY)
         {
            int dx=inc.x,dy=inc.y,cx=x,cy=y;
            for(int i=1;(i<value)&&(!OutRange(cx+=dx,cy+=dy));++i) if(map[cy][cx]!=0) queue.add(new Cell(cx,cy));
         }
      }
   }
}

To masz z kolejką na secie :P
Poprawiono

Tego chyba jeszcze nikt nie wymyślił, żeby użyć zbioru, jako struktury danych w trawersowaniu grafu:). Bo teraz Masz trawersowanie grafu (to samo co ja praktycznie, są różnice, ale w szczegółach). Niestety jest jakiś bug, dla małych n działa, ale, np. dla n = 140 sie nie zatrzymuje, dla wyższych jest Out of Memory Error: https://repl.it/@lion137/zeroArray2

EDIT2: Już miałem odszczekać, mój poprzedni, zresztą niezbyt grzeczny edit, ale @_13th_Dragon chyba, w tym przypadku, rzeczywiście nie Wiesz co Robisz; zatrzymuje się, owszem, ale daje błędne wyniki: https://repl.it/@lion137/zeroArray2

EDIT3: Nawiązując do komentarza @_13th_Dragon , wygląda na to, że działa i daje dobre wyniki, tylko jest niesamowicie wolny, dla nie tak wielkiego n, równego 90, czas wykonania ponad 65 sekund: https://repl.it/@lion137/BackJauntyTab; podczas, gdy tutaj: https://repl.it/@lion137/zaArrayListStack , trochę ponad 3 sekundy. Wpływ na performance na pewno ma użycie HashSeta, jako kolejki i swoja klasa (Cell), może JVM nie daje rady jej zoptymalizować.

EDIT4: Tamto powyżej jest nieważne, aktualne liczby wynoszą:
dla n = 240 , 159 sekund: https://repl.it/@lion137/BackJauntyTab
mój: około dwie i pół sekundy https://repl.it/@lion137/zaArrayListStack.