Problema backtracking

[schumy2000]

Guarda nella matrice 4 4 e ottengo come dici tu una configurazione di 5 torri

* * * * 2
* - - - 1
* * - * 2
- * - * 0


Mi costruisco una matrice di oggetti Field (o come vuoi chiamarlo)
e questo oggetto Field avrà degli attributi
boolean zonainteresse;
boolean sonotorre;
boolean sonogiacontrollato;


Parto dalla prima casella ed ogni volta mi devo fare queste domande per se stesso:
ripropongo lo schema:

* * * * 2
* - - - 1
* * - * 2
- * - * 0

partendo dalla prima casella

sono zona di interesse? si
sono già controllato? no

se abbiamo questa configurazione possiamo mettere una torre e vedere se nei suoi quattro vicini c'è una zona di interesse da controllare, che non sia già controllata o già torre, se c'è setti il valore di già controllato a true del suo vicino

Passiamo alla seconda casella:
sono zona di interesse? si
sono già controllato? si

quindi possiamo passare alla terza....

Così mi risulta che:
nella terza impianto una torre
la quarta è già controllata
la quinta devo impiantare una torre con la quale controllo la nona cella
la decima metto una torre con la quale controllo la quatttordicesima cella
e stesso discorso per tra la dodicesima e la sedicesima cella

Con questo metodo ottengo 5 torri da impiantare nello schema.

Fammi sapere se hai qualche domanda.

Ciao.

[marcos666]

Guarda nella matrice 4 4 e ottengo come dici tu una configurazione di 5 torri

* * * * 2
* - - - 1
* * - * 2
- * - * 0


Mi costruisco una matrice di oggetti Field (o come vuoi chiamarlo)
e questo oggetto Field avrà degli attributi
boolean zonainteresse;
boolean sonotorre;
boolean sonogiacontrollato;


Parto dalla prima casella ed ogni volta mi devo fare queste domande per se stesso:
ripropongo lo schema:

* * * * 2
* - - - 1
* * - * 2
- * - * 0

partendo dalla prima casella

sono zona di interesse? si
sono già controllato? no

se abbiamo questa configurazione possiamo mettere una torre e vedere se nei suoi quattro vicini c'è una zona di interesse da controllare, che non sia già controllata o già torre, se c'è setti il valore di già controllato a true del suo vicino

Passiamo alla seconda casella:
sono zona di interesse? si
sono già controllato? si

quindi possiamo passare alla terza....

Così mi risulta che:
nella terza impianto una torre
la quarta è già controllata
la quinta devo impiantare una torre con la quale controllo la nona cella
la decima metto una torre con la quale controllo la quatttordicesima cella
e stesso discorso per tra la dodicesima e la sedicesima cella

Con questo metodo ottengo 5 torri da impiantare nello schema.

Fammi sapere se hai qualche domanda.

Ciao.

grazie per la tua risposta, teoricamente ho capito il concetto ma un altra cosa è scrive il codice in JAVA, ad esempio non mi è chiaro come fare la funzione canADD o la ricorsione in questo caso

[marcos666]

grazie per la tua risposta, teoricamente ho capito il concetto ma un altra cosa è scrive il codice in JAVA, ad esempio non mi è chiaro come fare la funzione canADD o la ricorsione in questo caso

vedi per favore se sto facendo bene secondo le tue indicazioni:

public void control(String matrix2[][],boolean zonainteresse, boolean sonotorre, boolean sonogiacontrollato)
	{
		int cont=0;
		for(int i=0; i<riga; i++)
		{
			for(int j=0; j<colonna; j++)
			{
				if(matrix2[i][j].equals("*"))
				{
					zonainteresse=true;
					sonogiacontrollato=false;
					if(j+1 < colonna || i+1 < riga || (j-1<0) || !(i-1<0))
					{
						if(matrix2[i][j+1].equals("*") || matrix2[i+1][j].equals("*") || matrix2[i-1][j].equals("*") || matrix2[i][j-1].equals("*"))
						{
							if(!sonotorre && !sonogiacontrollato)
							{
								cont++;
							}
						}
					}
					
					
				}
			}
		}
	}