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); } }