NajboljiPut

import java.util.ArrayList;
import java.util.Comparator;

public class NajboljiPut {

	public static int s;
	public static int v;
	public static boolean[][] posecenost;
	public static int[][] mapa;
	public static final int polje = 0;
	public static final int zid = -11;
	public static final int cilj = -99;
	public static Put najboljiPut;
	public static Put test = new Put();
	public static ArrayList<Put> resenja = new ArrayList<Put>();
	public static Comparator<Put> c;

	public static void ucitajMapu(String imef) {
		if(Svetovid.testIn(imef)) {
			s = Svetovid.in(imef).readInt();
			v = Svetovid.in(imef).readInt();
			mapa = new int[v][s];
			posecenost = new boolean[v][s];
			for(int i = 0; i < v; i++) {
				for(int j = 0; j < s; j++) {
					mapa[i][j] = Svetovid.in(imef).readInt();
				}
			}
		}
	}

	public static void ispisiMapu() {
		for(int i = 0; i < v; i++) {
			for(int j = 0; j < s; j++) {
				System.out.println(mapa[i][j] + " ");
			}
			System.out.println();
		}
	}

	public static void nadjiPut(int i, int j) {
		if(i >= v || i < 0) {
			return ;
		}
		if(j >= s || j < 0) {
			return ;
		}
		if(mapa[i][j] == zid) {
			return ;
		}
		if(posecenost[i][j]) {
			return ;
		}
		if(mapa[i][j] == cilj) {
			Put kopija = test.kopiraj();
			kopija.dodajCvor(i, j, mapa[i][j]);
			resenja.add(kopija);
			if(najboljiPut == null || c.compare(test, najboljiPut) < 0) {
				najboljiPut = kopija;
			}
			return ;
		}

		posecenost[i][j] = true;
		test.dodajCvor(i, j, mapa[i][j]);

		nadjiPut(i-1, j);
		nadjiPut(i+1, j);
		nadjiPut(i, j+1);
		nadjiPut(i, j-1);

		test.izbrisiCvor();

		posecenost[i][j] = false;
	}

	public static void main(String[] args) {
		String imef = Svetovid.in.readLine("Unesite ime fajla: ");
		ucitajMapu(imef);

		int x;
		int y;
		do {
			x = Svetovid.in.readInt("Unesite x koordinatu: ");
		} while(x < 0 || x > v);
		do {
			y = Svetovid.in.readInt("Unesite y koordinatu: ");
		} while(y < 0 || y > s);

		int i = Svetovid.in.readInt("Unesite kakav put zelite da nadjete: ");

		switch(i) {
			case 1:
				c = Comparator.naturalOrder();
				break;
			case 2:
				c = new KomparatorPoVrednosti();
				break;
			case 3:
				c = new KomparatorPoNajvecemBlaguPojedinacno();
				break;
			case 4:
				c = new KomparatorPoBrojuBlaga();
			case 5:
				c = new KomparatorPoUzastopnomBlagu();
		}
		nadjiPut(x, y);

		if(najboljiPut != null) {
			System.out.println("Put postoji.");
			najboljiPut.ispisiPut();
			int br = 0;
			for(int k = 0; k < resenja.size(); k++) {
				if(resenja.get(k).uzastopnoBlagoMax >= 3) {
					br++;
				}
			}
			System.out.println("Broj resenja sa vise od tri uzastopna blaga je " + br);
		}
		else {
			System.out.println("Put ne postoji.");
		}
	}
}