## Wednesday, October 24, 2012

### Codechef: CodeWars 2012

Oct 24, 2012
A. Rainy Egypt          Solution.
B. Alice and Bob       Solution.
C. Rat Maze                Solution.
D. Chef Ash                Solution.

## Tutorial

### Solution:

Backtracking problem, from start point (0,0) go through each direction, then we will return 1 if it reach final corner (N-1, N-1), otherwise, return 0.

### Source Code:

import java.util.StringTokenizer;

/**
*
*/

/**
* @author antonio081014
* @time: Oct 24, 2012, 10:01:53 AM
*/
public class Main {

private int[][] matrix;
private int N;

private static final int[] dx = { 0, 1, -1, 0 };
private static final int[] dy = { 1, 0, 0, -1 };

public static void main(String[] args) throws Exception {
Main main = new Main();
main.run();
System.exit(0);
}

public void run() throws Exception {
boolean[][] mark = new boolean[N][N];
matrix = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
matrix[i][j] = Integer.parseInt(token.nextToken());
mark[i][j] = false;
}
}

System.out.println(dfs(0, 0, mark));
}

public int dfs(int x, int y, boolean[][] mark) {
if (x == N - 1 && y == N - 1)
return 1;
int count = 0;
for (int i = 0; i < 4; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (inBoundary(xx, yy) && matrix[xx][yy] == 0
&& mark[xx][yy] == false) {
mark[xx][yy] = true;
count += dfs(xx, yy, mark);
mark[xx][yy] = false;
}
}
return count;
}

public boolean inBoundary(int x, int y) {
return (x >= 0 && x < N && y >= 0 && y < N);
}
}