package spa2;

import java.util.*;

import java.io.BufferedReader;
import java.io.IOException;
import java.util.Comparator;

import org.svetovid.Svetovid;

public class PostojanjePuta {

	public static void main(String[] args) throws IOException {
		PostojanjePuta put = new PostojanjePuta();
		put.stampaj();
		Put putanja = new Put();
		PoBlagoPolj kom = new PoBlagoPolj();
		KompBlago komp2 = new KompBlago();
		KompDuz komp = new KompDuz();
		BrojUza kompb = new BrojUza();
		postojiPut2(0, 0, putanja, false);
		System.out.println("Putanja je " + put.optput);
		// System.out.println("Njena vrednost je " + put.optput.vrednost());
		// System.out.println("Broj uzastopnih polja sa blagom je " +
		// put.optput.getBrojuza());
	}

	public final static int IZLAZ = -99;
	public final static int ZID = -11;
	public final static int RUPA = -1;

	private static int visina, sirina;
	// matrica sa mapom
	private static int[][] mat;
	// mastrica posecenosti polja
	private static boolean[][] pos;
	private static Put optput; // pamti optimalni put
	private static boolean blago;
	private static boolean rupa;

	public PostojanjePuta() throws IOException {
		mat = ucitaj("lavrupe.txt");

	}

	private static int[][] ucitaj(String imeFajla) {
		if (Svetovid.testIn(imeFajla)) {
			visina = Svetovid.in(imeFajla).readInt();
			sirina = Svetovid.in(imeFajla).readInt();
			if (visina >= 0 && sirina >= 0) {
				mat = new int[visina][sirina];
				pos = new boolean[visina][sirina];
				for (int i = 0; i < visina; i++) {
					for (int j = 0; j < sirina; j++) {
						mat[i][j] = Svetovid.in(imeFajla).readInt();
					}
				}
				Svetovid.closeIn(imeFajla);
				return mat;
			}
		}
		return null;

	}

	public void stampaj() {
		for (int i = 0; i < visina; i++) {
			for (int j = 0; j < sirina; j++) {
				System.out.print(mat[i][j] + "\t");
			}
			System.out.println();
		}
	}

	public static void postojiPut3(int x, int y, Put putanja, int v) {
		if (x < 0 || x >= visina || y < 0 || y >= sirina) {
			return;
		}
		if (pos[x][y] || mat[x][y] == ZID) {
			return;
		}
		if (mat[x][y] == IZLAZ) {
			putanja.add(x, y, 0);
			optput = putanja.copy();
			putanja.remove();
			return;
		}
		if (mat[x][y] - v <= 3) {

		}

	}

	public static void postojiPut2(int x, int y, Put putanja, boolean rupa) { // zadatak sa preskakanjem rupa
		if (x < 0 || x >= visina || y < 0 || y >= sirina) {
			return;
		}
		if (pos[x][y] || mat[x][y] == ZID) {
			return;
		}
		if (mat[x][y] == IZLAZ) {
			putanja.add(x, y, 0);
			optput = putanja.copy();
			putanja.remove();
			return;
		}
		if (mat[x][y] == RUPA && !rupa) { // ako moze da preskoci
			pos[x][y] = true;
			rupa = true;
			putanja.add(x, y, mat[x][y]);

		} else if (mat[x][y] == RUPA && rupa) {
			rupa = true;
			return;
		}
		if (mat[x][y] != RUPA) {
			pos[x][y] = true;
			putanja.add(x, y, mat[x][y]);
			rupa = false;
		}
		postojiPut2(x + 1, y, putanja, rupa);
		postojiPut2(x, y - 1, putanja, rupa);
		postojiPut2(x - 1, y, putanja, rupa);
		postojiPut2(x, y + 1, putanja, rupa);
		pos[x][y] = false;
		rupa = false;
		putanja.remove();
		putanja.resetuj();
		return;

	}

	private static void postojiPut(int x, int y, Put putanja, Comparator<Put> komp, boolean blago) {
		if (x < 0 || x >= visina || y < 0 || y >= sirina) {
			return;
		}
		if (pos[x][y] || mat[x][y] == ZID) {
			return;
		}
		if (mat[x][y] == IZLAZ) {
			if (optput == null || komp.compare(putanja, putanja) < 0) {
				putanja.add(x, y, 0); // dodamo poslednje polje, tj izlaz
				optput = putanja.copy();
				System.out.println("Broj uzastopnih polja sa blagom je " + putanja.getBrojuza());
				if (putanja.getBrojuza() > 3) {
					System.out.println(putanja);
				}
				putanja.remove();
			}
			return;
		}

		pos[x][y] = true;
		if (mat[x][y] != 0) {
			if (blago) {
				putanja.povecaj(); // ako je prethodno bilo,ovo ce svakako biti
			}
			blago = true;

		} else {
			blago = false;
			putanja.resetuj();
		}
		putanja.add(x, y, mat[x][y]);
		postojiPut(x + 1, y, putanja, komp, blago);
		postojiPut(x, y - 1, putanja, komp, blago);
		postojiPut(x - 1, y, putanja, komp, blago);
		postojiPut(x, y + 1, putanja, komp, blago);

		pos[x][y] = false;
		putanja.remove();
		blago = false;
		putanja.resetuj();
		return;

	}

}


class KompDuz implements Comparator<Put> {

	@Override
	public int compare(Put r1, Put r2) {
		return r1.size() - r2.size();
	}

}

class BrojUza implements Comparator<Put> {
	public int compare(Put r1, Put r2) {
		return r2.getBrojuza() - r1.getBrojuza();
	}

}

class PoBlagoPolj implements Comparator<Put> {

	public int compare(Put r1, Put r2) {
		return r2.getBrojBlaga() - r1.getBrojBlaga();
	}

}

class KompBlago implements Comparator<Put> {

	@Override
	public int compare(Put r1, Put r2) {// - ide r1, + r2
		return -(r1.vrednost() - r2.vrednost());
	}

}

public class Put {

	public ArrayList<Polje> putanja;
	private int brojBlaga;
	private int brojuza;
	private int brojuzamax;
	private boolean skok;
	private int brojskokova;

	public Put() {
		putanja = new ArrayList<Polje>();
		brojBlaga = 0;
		brojuza = 0;
		brojuzamax = 0;
		skok = false;
		brojskokova = 0;
	}

	public String toString() {
		String s = "";
		int i = 0;
		if (putanja != null) {
			for (Polje tmp : putanja) {
				s += (tmp);
				s += "\n";
			}
		}
		return s;
	}

	public int getSkokovi() {
		return brojskokova;
	}

	public void skoci() {
		skok = true;
		brojskokova++;
	}

	public void resetuj() {
		if (brojuza != 0) {
			if (brojuzamax == 0)
				brojuzamax = brojuza;
			if (brojuzamax != 0 && brojuza > brojuzamax)
				brojuzamax = brojuza;
		}

		brojuza = 0;
	}

	public void povecaj() {
		brojuza++;
	}

	public int getBrojuza() {
		return brojuzamax;
	}

	public int getBrojBlaga() {
		return brojBlaga;
	}

	public int vrednost() {
		int n = 0;
		for (Polje m : putanja) {
			n += m.getV();
		}
		return n;
	}

	public void add(int x, int y, int v) {
		Polje novo = new Polje(x, y, v);
		if (v != 0)
			brojBlaga++;
		putanja.add(novo);
	}

	public void remove() {
		putanja.remove(putanja.size() - 1);
	}

	public int size() {
		return putanja.size();
	}

	public Put copy() {
		Put novi = new Put();
		novi.putanja = (ArrayList<Polje>) putanja.clone();
		return novi;
	}

}

class Polje {

	private int x, y, v;

	public int getX() {
		return x;

	}

	public String toString() {
		return "(" + x + " " + y + " (" + v + ")" + ")";
	}

	public void setX(int x) {
		this.x = x;
	}

	public int getY() {
		return y;
	}

	public void setV(int x) {
		this.v = x;
	}

	public int getV() {
		return v;
	}

	public void setY(int y) {
		this.y = y;
	}

	public Polje(int x, int y, int v) {
		this.x = x;
		this.y = y;
		this.v = v;
	}

}