import java.io.*;
import java.util.*;
import java.net.URL;
public class Labyrint
{
private static byte ÅPEN = 0;
private static byte VEGG = 1;
private static byte KRYSS = 2;
private static byte HØYRE = 3;
private static byte NED = 6;
private static byte VENSTRE = 9;
private static byte OPP = 12;
public static byte[][] hentLabyrint(String url) throws IOException
{
BufferedReader inn =
new BufferedReader(new InputStreamReader((new URL(url)).openStream()));
String[] dim = inn.readLine().split(" ");
int m = Integer.parseInt(dim[0]);
int n = Integer.parseInt(dim[1]);
byte[][] a = new byte[m][n];
for (int i = 0; i < m; i++)
{
String linje = inn.readLine();
for (int j = 0; j < n; j++)
{
if (linje.charAt(j) == '1') a[i][j] = 1;
}
}
inn.close();
return a;
}
public static boolean finnVei(byte[][] a, int i, int j, int iut, int jut)
{
a[i][j] = 2;
if (i == iut && j == jut) return true;
int m = a.length;
int n = a[0].length;
boolean funnet = false;
if (!funnet && j > 0 && a[i][j-1] == 0)
funnet = finnVei(a,i,j-1,iut,jut);
if (!funnet && i + 1 < m && a[i+1][j] == 0)
funnet = finnVei(a,i+1,j,iut,jut);
if (!funnet && j + 1 < n && a[i][j+1] == 0)
funnet = finnVei(a,i,j+1,iut,jut);
if (!funnet && i > 0 && a[i-1][j] == 0)
funnet = finnVei(a,i-1,j,iut,jut);
if (!funnet) a[i][j] = 0;
return funnet;
}
public static void skrivLabyrint(byte[][] a)
{
for (int i = 0; i < a.length; i++)
{
for (int j = 0; j < a[i].length; j++)
{
System.out.print(a[i][j]);
}
System.out.println();
}
}
public static void tilHTML(byte[][] a, String fil) throws IOException
{
PrintWriter ut = new PrintWriter(fil);
ut.println("<!DOCTYPE html PUBLIC \"-//W3C//DTD XHTML 1.0 Strict//EN\"");
ut.println("\"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd\">");
ut.println("<html xmlns=\"http://www.w3.org/1999/xhtml\" xml:lang=\"no\" lang=\"no\">");
ut.println("<head>");
ut.println("<title lang=\"no\">En labyrint</title>");
ut.println("<meta http-equiv = \"Content-Type\" content = \"text/html;charset=iso-8859-1\" />");
ut.println("</head>\n");
ut.println("<style type=\"text/css\" media=\"screen\">");
ut.println("<!--");
ut.println("td.bg");
ut.println("{");
ut.println(" background-color: #b0b0b0;");
ut.println("}\n");
ut.println("table.labyrint");
ut.println("{");
ut.println(" margin-right: auto; margin-left: auto;");
ut.println(" text-align: center;");
ut.println("}\n");
ut.println("table.labyrint td:first-child");
ut.println("{");
ut.println(" border-left: solid black 2px;");
ut.println(" width: 20px;");
ut.println("}\n");
ut.println("table.labyrint td:last-child ");
ut.println("{");
ut.println(" border-right: solid black 2px;");
ut.println(" width: 20px;");
ut.println("}\n");
ut.println("table.labyrint tr:first-child td");
ut.println("{");
ut.println(" border-right: solid black 1px;");
ut.println(" border-top: solid black 2px;");
ut.println(" border-bottom: solid black 1px;");
ut.println(" width: 20px;");
ut.println("}\n");
ut.println("table.labyrint tr:first-child td:last-child");
ut.println("{");
ut.println(" border-right: solid black 2px;");
ut.println(" border-top: solid black 2px;");
ut.println(" border-bottom: solid black 1px;");
ut.println(" width: 20px;");
ut.println("}\n");
ut.println("table.labyrint tr + tr td");
ut.println("{");
ut.println(" border-right: solid black 1px;");
ut.println(" border-bottom: solid black 1px;");
ut.println(" width: 20px;");
ut.println("}\n");
ut.println("table.labyrint tr:last-child td");
ut.println("{");
ut.println(" border-right: solid black 1px;");
ut.println(" border-bottom: solid black 2px;");
ut.println(" width: 20px;");
ut.println("}\n");
ut.println("table.labyrint tr:last-child td:last-child");
ut.println("{");
ut.println(" border-right: solid black 2px;");
ut.println(" width: 20px;");
ut.println("}\n");
ut.println("-->");
ut.println("</style>\n");
ut.println("<body>");
ut.println("<br /> <br /> \n");
ut.println("<table class=\"labyrint\" border=\"0\" cellspacing=\"0\" cellpadding=\"0\">");
int m = a.length;
int n = a[0].length;
for (int i = 0; i < m; i++)
{
ut.println("<tr>");
for (int j = 0; j < n; j++)
{
if (a[i][j] == 1)
ut.println(" <td class=\"bg\"> </td>");
else if (a[i][j] == 2)
ut.println(" <td>×</td>");
else
ut.println(" <td> </td>");
}
ut.println("</tr>");
}
ut.println("</table>");
ut.println("</body>");
ut.println("</html>");
ut.close();
}
public static void finnKortestVei(byte[][] a, int i, int j, int iut, int jut,
int lengde, int[] kortest)
{
a[i][j] = 2;
if (i == iut && j == jut)
{
if (lengde < kortest[0]) kortest[0] = lengde;
}
int m = a.length, n = a[0].length;
if (j + 1 < n && a[i][j+1] == 0)
finnKortestVei(a,i,j+1,iut,jut,lengde+1,kortest);
if (i + 1 < m && a[i+1][j] == 0)
finnKortestVei(a,i+1,j,iut,jut,lengde+1,kortest);
if (j > 0 && a[i][j-1] == 0)
finnKortestVei(a,i,j-1,iut,jut,lengde+1,kortest);
if (i > 0 && a[i-1][j] == 0)
finnKortestVei(a,i-1,j,iut,jut,lengde+1,kortest);
a[i][j] = 0;
}
}