Codechef: CodeWars 2012

Oct 24, 2012

A. Rainy Egypt          Solution.
B. Alice and Bob       Solution.

C. Rat Maze                Solution.
D. Chef Ash                Solution.

Tutorial

Problem 1:

Solution:

Source Code:

Problem 2:

Solution:

Source Code:

Problem 3:

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.io.BufferedReader;
import java.io.InputStreamReader;
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 {
 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 N = Integer.parseInt(br.readLine());
 boolean[][] mark = new boolean[N][N];
 matrix = new int[N][N];
 for (int i = 0; i < N; i++) {
     StringTokenizer token = new StringTokenizer(br.readLine());
     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);
    }
}

Problem 4:

Solution:

Source Code: