//Jitu Das
//Intermediate-5
//Contest 4
//MBHS
//7096
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class ACSLContest4Int {
static
boolean[][] nodes;
public
static String readString(String prompt) {
try {
System.out.print(prompt);
return (new BufferedReader(new
InputStreamReader(System.in))).readLine();
}
catch (Exception e) {
return "";
}
}
public
static boolean[][] ArrayCopy(boolean[][] src) {
boolean[][] dest = new
boolean[src.length][src[0].length];
for (int i = 0; i < src.length;
i++)
for (int j = 0; j <
src[0].length; j++)
dest[i][j]
= src[i][j];
return dest;
}
public
static int getNumPaths(boolean[][] unused, int rowStart, int colStart, int
rowEnd, int colEnd) {
if (rowStart == rowEnd &&
colStart == colEnd) return 1;
if (!unused[rowStart][colStart])
return 0;
unused[rowStart][colStart] = false;
int numPaths = 0;
if (rowStart-1 >= 0)
if (unused[rowStart-1][colStart])
numPaths
+= getNumPaths(ArrayCopy(unused), rowStart-1, colStart, rowEnd, colEnd);
if (rowStart+1 < nodes.length)
if (unused[rowStart+1][colStart])
numPaths
+= getNumPaths(ArrayCopy(unused), rowStart+1, colStart, rowEnd, colEnd);
if (colStart-1 >= 0)
if (unused[rowStart][colStart-1])
numPaths
+= getNumPaths(ArrayCopy(unused), rowStart, colStart-1, rowEnd, colEnd);
if (colStart+1 < nodes[0].length)
if (unused[rowStart][colStart+1])
numPaths
+= getNumPaths(ArrayCopy(unused), rowStart, colStart+1, rowEnd, colEnd);
return numPaths;
}
public
static void main(String[] args) {
String nodeStr = "",
readStr = "";
nodeStr = readString("Enter the
nodes: ") + ",";
int row = -1, col = -1, maxRows = 0,
maxCols = 0;
for (int i = 0; i <
nodeStr.length(); i++) {
char curChar = nodeStr.charAt(i);
if (curChar != ',') readStr +=
curChar;
else if (readStr.charAt(0) == '0')
break;
else {
if
(row == -1) row = Integer.parseInt(readStr)-1;
else
{
col = Integer.parseInt(readStr)-1;
maxRows = Math.max(row, maxRows);
maxCols = Math.max(col, maxCols);
row = -1; col = -1;
}
readStr
= "";
}
}
nodes = new
boolean[maxRows+1][maxCols+1];
readStr = "";
row = -1; col = -1;
for (int i = 0; i < nodeStr.length();
i++) {
char curChar = nodeStr.charAt(i);
if (curChar != ',') readStr +=
curChar;
else if (readStr.charAt(0) == '0')
break;
else {
if
(row == -1) row = Integer.parseInt(readStr)-1;
else
{
col = Integer.parseInt(readStr)-1;
nodes[row][col] = true;
row = -1; col = -1;
}
readStr
= "";
}
}
for (int program = 0; program <
5; program++) {
nodeStr = readString("Enter
points: ") + ",";
int rowStart = -1, colStart = -1;
int rowEnd = -1, colEnd = -1;
readStr = "";
for (int i = 0; i <
nodeStr.length(); i++) {
char
curChar = nodeStr.charAt(i);
if
(curChar != ',') readStr += curChar;
else
{
if (colStart == -1) {
if
(rowStart == -1) rowStart = Integer.parseInt(readStr)-1;
else
colStart = Integer.parseInt(readStr)-1;
}
else {
if
(rowEnd == -1) rowEnd = Integer.parseInt(readStr)-1;
else
colEnd = Integer.parseInt(readStr)-1;
}
readStr = "";
}
}
int numPaths =
getNumPaths(ArrayCopy(nodes), rowStart, colStart, rowEnd, colEnd);
System.out.println((numPaths>0)?Integer.toString(numPaths):"NONE");
}
}
}