[Ansi C] Fosse di una matrice

[Monkey13]

Salve a tutti! Sono sempre io e l'Ansi C.

Ho difficoltà a trovare un algoritmo efficiente per questo problema:

Dati un array-2 a e due interi r e c, indicare se a[r][c] è una buca (o fossa) (cioè se a[r][c] è < di ogni elemento con il quale confina). Risolvere il problema unificando la gestione di tutti gli elementi che appartengono al bordo dell'array-2 e senza sovradimensionare l'array-2.

Esempio :
0 1 2 c
-------
0 |1 6 5
1 |9 7 9
2 |0 6 3

r

Input : r=2 c=2 è fossa ! poichè tutti gli elementi confinanti cioè 6 7 9 sono maggiori rispetto a lui.
Inizialmente avevo notato un modo per farlo, ma solo per le fosse "interne" alla matrice.
Ma i bordi mi restano ignoti. mi potreste aiutare? grazie mille

[Xerex]

Fammi capire...tu devi controllare se intorno ad una "casella" data come input, ci sono tutti valori maggiori?

se è così con due cicli innestati dove incrementi nel primo le righe partendo da max(0,x-1) fino a min (n,x+1) e nel secondo le colonne con lo stesso sistema ottieni quello che vuoi, uscendo dal ciclo nel caso il valore controllato sia > di quello con il quale lo stai confrontando...

[M@ttia]

Eh il suo problema credo si ponga nel caso in cui sei su una casella "bordo" e non hai niente ad es. a "destra"...

Potresti fare ogni volta un controllo... (Se il numero della colonna attuale è diverso dal numero di colonne max. allora esegui il controllo a destra, ecc.)

[M@ttia]

Esplicitamente:

Hai una Tabella #Righe x #Colonne (convenzione: la prima riga è la Numero 0) e vuoi cercare l'elemento a[r][c]:

Codice: Seleziona tutto

int A = a[r][c];

if(r != 0)                                 // Controllo le 3 Sopra
{
  if(A >= a[r-1][c])                       {return "Non è una Buca!";};
  if(c !=0 && A >= a[r-1][c-1];)           {return "Non è una Buca!";};
  if(c != #Colonne-1 && A >= a[r-1][c+1])  {return "Non è una Buca!";};
}

if(r != #Righe-1)                          // Controllo le 3 Sotto
{
  if(A >= a[r+1][c];)                      {return "Non è una Buca!";};
  if(c !=0 && A >= a[r+1][c-1];            {return "Non è una Buca!";};
  if(c != #Colonne-1 && A >= a[r+1][c+1];  {return "Non è una Buca!";};
}
                                           // Controllo le 2 Laterali

if(c != 0 && A >= a[r][c-1];)              {return "Non è una Buca!";};
if(c != #Colonne-1 && A >= a[r][c+1];)     {return "Non è una Buca!";};

return "È una Buca!";


[Xerex]

Eh il suo problema credo si ponga nel caso in cui sei su una casella "bordo" e non hai niente ad es. a "destra"...

Potresti fare ogni volta un controllo... (Se il numero della colonna attuale è diverso dal numero di colonne max. allora esegui il controllo a destra, ecc.)

il mio max(o,n-1) e min(n,x+1) avevo quel significa...

[Monkey13]

Esplicitamente:

Hai una Tabella #Righe x #Colonne (convenzione: la prima riga è la Numero 0) e vuoi cercare l'elemento a[r][c]:

Codice: Seleziona tutto

int A = a[r][c];

if(r != 0)                                 // Controllo le 3 Sopra
{
  if(A >= a[r-1][c])                       {return "Non è una Buca!";};
  if(c !=0 && A >= a[r-1][c-1];)           {return "Non è una Buca!";};
  if(c != #Colonne-1 && A >= a[r-1][c+1])  {return "Non è una Buca!";};
}

if(r != #Righe-1)                          // Controllo le 3 Sotto
{
  if(A >= a[r+1][c];)                      {return "Non è una Buca!";};
  if(c !=0 && A >= a[r+1][c-1];            {return "Non è una Buca!";};
  if(c != #Colonne-1 && A >= a[r+1][c+1];  {return "Non è una Buca!";};
}
                                           // Controllo le 2 Laterali

if(c != 0 && A >= a[r][c-1];)              {return "Non è una Buca!";};
if(c != #Colonne-1 && A >= a[r][c+1];)     {return "Non è una Buca!";};

return "È una Buca!";


Grazie per risposte.
M@ttia ha capito cosa volevo intendere, ma mi sembra strano che non si usino cicli o altre istruzioni di controllo...
Comunque adesso guarderò. Vi ringrazio.. Ciao!!

[Monkey13]

Eh il suo problema credo si ponga nel caso in cui sei su una casella "bordo" e non hai niente ad es. a "destra"...

Potresti fare ogni volta un controllo... (Se il numero della colonna attuale è diverso dal numero di colonne max. allora esegui il controllo a destra, ecc.)

il mio max(o,n-1) e min(n,x+1) avevo quel significa...

potresti realizzare la tua idea?... perché non ho capito molto bene..

[M@ttia]

Eh il suo problema credo si ponga nel caso in cui sei su una casella "bordo" e non hai niente ad es. a "destra"...

Potresti fare ogni volta un controllo... (Se il numero della colonna attuale è diverso dal numero di colonne max. allora esegui il controllo a destra, ecc.)

il mio max(o,n-1) e min(n,x+1) avevo quel significa...

[Xerex]

mmmm...no :-)

è molto semplice:
se vuoi scorrere tutta una matrice, ti servono 2 cicli che scorrono tutte le righe e tutte le colonne.
bene, a te interessa invece controllare un quadrato con centro il punto delle coordinate date.
I punti particolari sono quelli che appartengono ai bordi della matrice originale quindi, quando farai il controllo, fatto sempre con i due cicli innestati dovrai scegliere le coordinate x ed y che saranno i tuoi limiti, in base al massimo tra 0 ed x-1(cioè il punto a sinistra del tuo centro) ed il minimo tra n ed x+1 dove n è il numero di righe della mat originale ed x+1 è il punto più a destra del punto che stai analizzando.
La stessa cosa la devi fare in alto ed in basso nell'altro ciclo

[Monkey13]

Risolvere il problema unificando la gestione di tutti gli elementi che appartengono al bordo dell'array-2 e senza sovradimensionare l'array-2.

E' questo il punto, la soluzione di M@ttia non rispetta questa condizione.. praticamente dovrebbe valutare i bordi con un'unica condizione come dice il testo. Boh aiutatemi non ci capiscono più niente..

[Xerex]

Io te l'ho detto!

Due cicli innestati, sta a te trovare le condizioni da inserire nell'intestazione del ciclo...
saranno non più di 15 righe di codice

[Monkey13]

Ok grazie a tutti! dopo mille anni ci sono arrivato!!!

Codice: Seleziona tutto

int Fossa_Matrice (const int (*a) [N2], int n1, int n2, int r, int c) {
    int i, j;
    int c=0;
    for (i=r-1; i<=r+1; i++)
        for (j=c-1; j<=c+1; j++)
            if ((i>=0)&&(i<n1)&&(j>=0)&&(j<n2)&&((i!=r)&&(j!=c)))
               if(a[r][c]>a[i][j])
                   return o;
    return 1;
} /* controllo */


ringrazio i ragionamenti di tutti..
Sempre i migliori...