Psst.. new poll here.
[email protected] webmail now available. Want one? Go here.
Cannot use outlook/hotmail/live here to register as they blocking our mail servers. #microsoftdeez
Obey the Epel!
Paste
Pasted as Java by registered user Zwick ( 5 years ago )
public static boolean findSum(int[][] mat, int sum, int[][] path)
{
lowerThanSum(mat, sum, path, 0);
if (runPath(mat, sum, path, 0, 0))
return true;
else
{
int[][] failure = new int[path.length][path[0].length];
path = failure;
return false;
}
}
private static boolean runPath(int[][] mat, int sum, int[][] path, int row, int col)
{
if (isInBound(mat, path, row, col))
{
if (mat[row][col] == sum)
{
path[row][col] = 1;
return true;
}
else if (mat[row][col] < sum)
{
if (!(runPath(mat, sum - mat[row][col], path, row - 1, col, success) || runPath(mat, sum - mat[row][col], path, row, col - 1, success) || runPath(mat, sum - mat[row][col], path, row + 1, col, success) || runPath(mat, sum - mat[row][col], path, row, col + 1, success)))
path[row][col] = 0;
else
{
path[row][col] = 1;
return (runPath(mat, sum - mat[row][col], path, row - 1, col, success) || runPath(mat, sum - mat[row][col], path, row, col - 1, success) || runPath(mat, sum - mat[row][col], path, row + 1, col, success) || runPath(mat, sum - mat[row][col], path, row, col + 1, success));
}
}
}
return false;
}
private static boolean isInBound(int[][] mat, int[][] path, int row, int col)
{
if (col < mat[0].length && col >= 0 && row < mat.length && row >= 0)
if (path[row][col] == 0)
return true;
return false;
}
private static void lowerThanSum(int[][] mat, int sum, int[][] path, int row)
{
if (row == mat.length)
return;
lowerThanSum(mat, sum, path, row, 0);
lowerThanSum(mat, sum, path, row + 1);
}
private static void lowerThanSum(int[][] mat, int sum, int[][] path, int row, int col)
{
if (col == mat[row].length)
return;
if (mat[row][col] <= sum)
path[row][col] = 1;
lowerThanSum(mat, sum, path, row, col + 1);
}
Revise this Paste