[java] info su controllo matrice

[doricum]

Ciao,
ho un problema, in una matrice ho memorizzato dei valori interi compresi in un range tra 0 e 2. devo riuscire a controllare in tutta la matrice sia orizzontale, verticale che in diagonale se esistono ad esempio una terna di 1 o di 2.
ma non solo , se esiste una terna e subito prima o subito dopo c'è uno 0 allora mi restituisce la posizione dello 0 ; ad esempio :
001112112 -> return 2 oppure 0021110221 -> return 7

qualcuno sa darmi un suggerimento su come poter implementare un algoritmo o se esiste qualcosa di simile in giro ?

grazie mille

[Mixmar]

La prima idea che mi viene in mente è quella di ridurre la matrice ad un insieme di "stringhe-vettori", e poi di utilizzare le funzioni di ricerca delle stringhe per trovare le terne e gli zeri.

Per esempio, potresti trasformare tutte le righe in stringhe, ottenendo un array di stringhe in cui ogni carattere è una cifra, e poi effettuare una ricerca del tipo:

posizioneTerna1 = "001112112...".indexOf("111");

per trovare la prima terna di "1", poi controlli se i caratteri precedente seguenti sono zero, con ".substring()". Quindi, procedi nella stringa-vettore cercando la prossima occorrenza dellla stessa terna fino a finire la stringa (se non ricordo male, basta passare un parametro in più ad indexOf, così:

posizioneTerna2 = "001112112...".indexOf("111", posizioneTerna1)

Dovresti iterare su ogni terna che cerchi, per ogni stringa-vettore.

Poi ripeti tutto, questa volta trasformando le colonne in stringhe.

Infine, ripeti il procedimento per l'ultima volta sulle diagonali (tra parentesi, non ho capito se ti interessino solo le diagonali principali o anche le altre).

Questo metodo non è computazionalmente molto efficiente (troppe conversioni a stringa / ricerche): penso che si possa fare di meglio, visti gli stretti limiti matematici del problema (l'insieme dei possibili valori assunti dalle celle della matrice è limitato, ricerchi una sequenza regolare...). Purtroppo, non saprei come creare un metodo più efficiente sfruttando la matematica: provaci tu, serve ingegnosità e un ripasso dell'algebra delle matrici.

[lovaz]

Oppure iteri su tutti gli elementi e consideri di volta in volta il quadratino 9x9

[doricum]

Grazie mille per il vostro prezioso aiuto!
il controllo devo farlo su tutte le diagonali e forse la gestione diventa un pò più complicata.

[banryu79]

Originariamente inviato da doricum

Grazie mille per il vostro prezioso aiuto!
il controllo devo farlo su tutte le diagonali e forse la gestione diventa un pò più complicata.

Prendendo spunto da un esempio di classe per gestire una matrice che avevo postato in un vechcio thread ed aggiungendo solo lo stretto neccessario (pigrizia & fretta rules!) sono giunto a questo:

Una classe di routine, per rappresentare un singolo "match"

package matrix;

/**
 *
 * @author francesco
 */
public class Match
{
    private final int ROW, COLUMN;
    private final String TYPE;
    private final Matrix REF;

    public Match(int row, int col, String type, Matrix mat) {
        ROW = row;
        COLUMN = col;
        TYPE = type;
        REF = mat;
    }

    public int getROW() {
        return ROW;
    }

    public int getCOLUMN() {
        return COLUMN;
    }

    public String getTYPE() {
        return TYPE;
    }

    public Matrix getMATRIX() {
        return REF;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("@[").append(ROW).append("][").append(COLUMN).append("]->").append(TYPE)
          .append("=").append(REF.getValueAt(ROW, COLUMN));
        return sb.toString();
    }
}

La classe matrice. Nel main c'è un esempio di utilizzo.

package matrix;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author francesco
 */
public class Matrix
{
    private final int ROWS, COLUMNS;
    private boolean initialized;
    private final int[][]DATA;

    public Matrix(int r, int c) {
        if (r<1 || c<1)
            throw new IllegalArgumentException("Il valore di righe e colunne deve essere maggiore di zero.");
        
        ROWS = r;
        COLUMNS = c;
        DATA = new int[ROWS][COLUMNS];
    }

    public Matrix(int data[][]) {
        if (data==null || data.length<1 || data[0].length<1)
            throw new IllegalArgumentException("Impossibile costruire una matrice di zero righe o " +
                    "zero colonne.");

        ROWS = data.length;
        COLUMNS = data[0].length;
        DATA = new int[ROWS][COLUMNS];
        initData(data);
    }

    /** torna una copia dei dati nella matrice */
    public int[][] getData() {
        int[][] copyData = new int[ROWS][COLUMNS];
        for (int r=0; r<ROWS; r++)
            for (int c=0; c<COLUMNS; c++) copyData[r][c] = DATA[r][c];
        return copyData;
    }

    /** inizializza la matrice */
    public void initData(int newdata[][]) {
        if (initialized)
            throw new RuntimeException("Impossibile modificare la matrice");

        initialized = true;
        for (int r=0; r<ROWS; r++)
            for (int c=0; c<COLUMNS; c++) DATA[r][c] = newdata[r][c];
    }

    public int getValueAt(int row, int column) {
        if (!isRowValid(row) || !isColumnValid(column))
            throw new IllegalArgumentException("Valore di riga o di colonna fuori dal range valido");

        return DATA[row][column];
    }

    private boolean isRowValid(int row) {
        return  row>=0 && row<ROWS;
    }

    private boolean isColumnValid(int column) {
        return  column>=0 && column<COLUMNS;
    }

    /** ottieni la matrice trasposta di questa matrice */
    public Matrix getTrasposta() {
        Matrix tras = new Matrix(COLUMNS, ROWS);
        for (int c=0; c<COLUMNS; c++)
            for (int r=0; r<ROWS; r++) tras.DATA[c][r] = DATA[r][c];
        return tras;
    }

    /** 
     * Ottieni tutti i match nelle righe del pattern rappresentato dal valore V ripetuto per N volte.
     * Gli elementi di una riga N sono indirizzati da ogni [N][c] valido, con c -> 0, c+1, ...
     */
    public List<Match> findRowsMatch(final int V, final int N) {
        List<Match> matches = new ArrayList<Match>();
        for (int r=0; r<ROWS; r++) {
            int count = 0;
            for (int c=0; c<COLUMNS; c++) {
                int elem = DATA[r][c];

                if (elem == V)
                    count++; 
                else
                    count = 0;

                if (count == N) {
                    Match m = new Match(r, c-(N-1), "Hor", this);
                    matches.add(m);
                    count = 0;
                }
            }
        }
        return matches;
    }

    /**
     * Ottieni tutti i match nelle colonne del pattern rappresentato dal valore V ripetuto per N volte.
     * Gli elementi di una colonna N sono indirizzati da ogni [r][N] valido, con r -> 0, r+1, ...
     */
     public List<Match> findColumnsMatch(final int V, final int N) {
        List<Match> matches = new ArrayList<Match>();
        for (int c=0; c<COLUMNS; c++) {

            int count = 0;
            for (int r=0; r<ROWS; r++) {
                int elem = DATA[r][c];

                if (elem == V)
                    count++;
                else
                    count = 0;

                if (count == N) {
                    Match m = new Match(r-(N-1), c, "Col", this);
                    matches.add(m);
                    count = 0;
                }
            }

        }
        return matches;
     }

    /**
     * Ottieni tutti i match nelle diagonali del pattern rappresentato dal valore V ripetuto per N volte.
     * Le diagonali vengono controllate rispetto alla regione NxN riferita ad un elemento [er][ec] e definita
     * a sua volta come la matrice NxN degli [er+N-1][ec+N-1] elementi.
     */
    public List<Match> findDiagonalMatch(final int V, final int N) {
        List<Match> matches = new ArrayList<Match>();
        for (int r=0; r<ROWS; r++) {
            for (int c=0; c<COLUMNS; c++) {
                // get the square sub-matrix (region)
                Matrix region = getRegionFrom(r,c,N);
                if (region == null)
                continue;
                // check first diagonal
                for (int count=0, i=0; i<N; i++) {
                    int elem = region.getValueAt(i,i);
                    if (elem == V)
                        count++;
                    else
                        count = 0;
                    if (count == N) {
                        Match m = new Match(r, c, "Diag1", this);
                        matches.add(m);
                        count = 0;
                    }
                }
                // check second diagonal
                for (int count=0, rr=N-1, rc=0;  rc<N;  rr--, rc++) {
                    int elem = region.getValueAt(rr,rc);
                    if (elem == V)
                        count++;
                    else
                        count = 0;
                    if (count == N) {
                        Match m = new Match(r, c+(N-1), "Diag2", this);
                        matches.add(m);
                        count = 0;
                    }
                }
            }
        }
        return matches;
    }
    
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int r=0; r<ROWS; r++) {
            for (int c=0; c<COLUMNS; c++) sb.append(DATA[r][c]).append(".");
            sb.append("\n");
        }
        return sb.toString();
    }

    /** Return the sub-matrix of NxN elements starting from element[r][c] if possible, otherwise null*/
    public Matrix getRegionFrom(int r, int c, int N) {
        if (isRowValid(r+N-1) && isColumnValid(c+N-1)) {
            int[][] data = new int[N][N];
            for (int newR=0, oldR=r;  oldR<r+N;  newR++, oldR++)
                for (int newC=0, oldC=c;  oldC<c+N;  newC++, oldC++)
                    data[newR][newC] = DATA[oldR][oldC];
            return new Matrix(data);
        }
        else
            return null;
    }


    // TEST
    public static void main(String... argv) {
        int[][]data = { {1,1,1,0,0,0,0,0,2,2,2,0,0,0,0,0},
                        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                        {0,0,0,0,2,2,2,0,0,0,0,0,0,0,0,0},
                        {0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0},
                        {0,0,0,0,0,1,1,0,0,2,0,0,0,0,0,0},
                        {0,0,0,0,0,1,0,0,0,0,2,0,0,1,1,1},
                        {0,0,0,0,1,0,0,0,0,0,0,2,0,0,1,1},
                        {0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1}, };
        Matrix m = new Matrix(data);
        System.out.println("matrice originale:\n"+m);
        //System.out.println("matrice trasposta:\n"+m.getTrasposta());
        int value, count;
        List<Match> matches;

        value = 2;
        count = 3;
        matches = m.findRowsMatch(value, count);
        for (Match mt : matches)
            System.out.println(mt);

        value = 1;
        count = 3;
        matches = m.findColumnsMatch(value, count);
        for (Match mt : matches)
            System.out.println(mt);

        value = 1;
        count = 3;
        matches = m.findDiagonalMatch(value, count);
        for (Match mt : matches)
            System.out.println(mt);
    }
}

Dovrebbe stampare:

matrice originale:
1.1.1.0.0.0.0.0.2.2.2.0.0.0.0.0.
0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.
0.0.0.0.2.2.2.0.0.0.0.0.0.0.0.0.
0.0.0.0.0.1.0.0.0.0.0.0.0.0.0.0.
0.0.0.0.0.1.1.0.0.2.0.0.0.0.0.0.
0.0.0.0.0.1.0.0.0.0.2.0.0.1.1.1.
0.0.0.0.1.0.0.0.0.0.0.2.0.0.1.1.
0.0.0.0.0.0.0.0.0.0.0.0.0.1.0.1.

@[0][8]->Hor=2
@[2][4]->Hor=2
@[3][5]->Col=1
@[5][15]->Col=1
@[4][6]->Diag2=1
@[5][13]->Diag1=1
@[5][15]->Diag2=1

Fa molto schifo ma funziona.
(Rifattorizzare e pulire sarebbe d'obbligo, ma ho scritto + o - al volo e questo ho partorito ):