Salve a tutti, all'università ci hanno dato questo compito che dovremo risolvere, a quanto ho capito
potrei risolverlo con il backtracking. ho cercato un po di informazione su internet per vedere il funzionamento pero non so come applicarlo al problema che ci hanno dato, quindi vi chiedo un consiglio per cominciare, ho fatto la lettura da input della matrice e gli altri dati ma non so come applicare backtracking.
il compito lo dovrei svolgere in java
grazie
Sia M una matrice di dimensione n*m con n, m > 0 rappresentante il territorio da controllare. Ogni cella di M può contenere uno dei caratteri dell’insieme { *, - }: il carattere * indica una zona d’interesse che deve essere controllata, mentre il carattere - indica uno spazio vuoto.
È possibile costruire una torre di sorveglianza nelle zone d’interesse.
Se si costruisce una torre in una zona d’interesse (i, j) allora:
- la zona d’interesse (i, j) è controllata, e
- una zona d’interesse tra (i, j+1), (i, j-1), (i+1, j) e (i-1, j) è controllata a sua volta, secondo l’orientamento della torre.
Non c’è un limite sul numero di torri da costruire ma l’Imperatore ha espressamente chiesto di costruirne il minore numero possibile.
Implementare un programma che restituisca il numero minimo di torri da costruire sul territorio in modo da controllare tutte le zone d’interesse.
Input
La lettura dovrà avvenire da standard input.
L’input consiste in un numero i (i ≥ 1) di test, rappresentanti i territori da controllare; per ogni territorio, il formato è il seguente:
- la prima riga contiene la parola chiave territory e un numero j (separati da spazio),
rappresentate l’inizio del j-esimo territorio;
- la seconda riga contiene i numeri n m, dove n è il numero di righe della matrice e m il
numero di colonne della matrice;
- le successive n righe sono nel formato c1 c2 ... cm, ovvero un numero m di caratteri separati
da uno spazio; ogni riga con questo formato rappresenta una riga della matrice.
Questo formato vale per tutti i test. L’input termina con la stringa -1.
Si assumi che l’input sia corretto e che non ci siano caratteri diversi da * o - nella matrice.
Output
L’output del programma deve avvenire su standard output; per ogni test, l’output deve essere nel seguente formato:
- la prima riga contiene la parola chiave result e un numero k (separati da uno spazio),
rappresentanti il k-esimo test;
- la seconda riga contiene un numero a rappresentante il numero minimo di torri da costruire
per controllare tutte le zone d’interesse.
Esempio input
territory 1
3 2
* *
- *
* -
territory 2 4 4
**** *--- **-* -*-* territory 3 37 *-*---* **-**-- *--**-* -1
Esempio output
result 1
3
result 2
5
result 3 8
io ho provato ad scrivere questo ma mi sa che sono lontano dalla sol.
mi manca di implementare il candd
package x;
import java.awt.Point;
import java.io.BufferedReader;
import java.io.Console;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.ArrayList;
public class Matrice {
String matrix[][];
int riga, colonna;
int cont;
public Matrice(int riga, int colonna) {
this.colonna = colonna;
this.riga = riga;
cont = 0;
matrix = new String[riga][colonna];
}
public void input(BufferedReader input) throws IOException {
String array[] = new String[colonna];
for (int i = 0; i < riga; i++) {
String x = input.readLine();
array = x.split(" ");
for (int j = 0; j < colonna; j++) {
matrix[i][j] = array[j];
}
}
}
ArrayList<Point> punti = new ArrayList<Point>();
int p = 0;
private int soluzionePeggiore;
public boolean risolved(ArrayList<Point> punt) {
while (p < punt.size()) {
int i = (int) punt.get(p).getX();
int j = (int) punt.get(p).getY();
if (canAdd(i, j, punt)) {
aggiungiSol(i, j, punt);
if (isComplete(punti)) {
return true;
} else if (risolved(punt)) {
return true;
}
remove(i, j, punt);
p++;
} else {
p++;
}
}
return false;
}
private void remove(int i, int j, ArrayList<Point> punt) {
for (int x = 0; x < punt.size(); x++) {
if (punt.get(x).getX() == i && punt.get(x).getY() == j)
punt.remove(x);
}
}
private boolean isComplete(ArrayList<Point> punti2) {
return (p <soluzionePeggiore);
}
private void aggiungiSol(int i, int j, ArrayList<Point> punt) {
punt.add(new Point(i, j));
}
private boolean canAdd(int i, int j, ArrayList<Point> punt) {
return true;
}
public int numeroTorri() {
for (int i = 0; i < riga; i++) {
for (int j = 0; j < colonna; j++) {
if (matrix[i][j].equals("*")) {
punti.add(new Point(i, j));
}
}
}
soluzionePeggiore = punti.size();
risolved(punti);
return punti.size();
}
public void stampa() {
System.out.println();
for (int i = 0; i < riga; i++) {
for (int j = 0; j < colonna; j++) {
System.out.print(matrix[i][j]);
}
System.out.println();
}
}
}
Rispondi quotando
Originariamente inviata da schumy2000
