Curling 2.0 (POJ 3009)
Use depth first search. Note that you can throw the stone in a direction only if there are at least one empty cell ahead.
import java.io.*;
import java.util.*;
public class Curling2 {
static private int[] dx = {-1, 0, 1, 0};
static private int[] dy = {0, 1, 0, -1};
private static int findSolution(int[][] board, int sx, int sy, int d, int limit) {
if (limit >= 10) return Integer.MAX_VALUE;
int h = board.length;
int w = board[0].length;
int nx, ny;
boolean flag = false;
while (true) {
nx = sx + dx[d];
ny = sy + dy[d];
if (nx < 0 || ny < 0 || nx >= h || ny >= w) {
return Integer.MAX_VALUE;
}
if (board[nx][ny] == 3) {
return 1;
}
if (board[nx][ny] == 1) {
if (!flag) return Integer.MAX_VALUE;
break;
}
sx = nx;
sy = ny;
flag = true;
}
board[nx][ny] = 0;
int min = Integer.MAX_VALUE;
for (int direction = 0; direction < 4; direction++) {
int res = findSolution(board, sx, sy, direction, limit + 1);
min = Math.min(min, res);
}
board[nx][ny] = 1;
if (min == Integer.MAX_VALUE) return min;
else return min + 1;
}
private static void solve(int[][] board, int sx, int sy) {
int solution = Integer.MAX_VALUE;
for (int direction = 0; direction < 4; direction++) {
int res = findSolution(board, sx, sy, direction, 0);
solution = Math.min(solution, res);
}
if (solution == Integer.MAX_VALUE) System.out.println(-1);
else System.out.println(solution);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (true) {
int W = in.nextInt(), H = in.nextInt();
if (W == 0 && H == 0) return;
int[][] board = new int[H][W];
int sx = -1, sy = -1;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
board[i][j] = in.nextInt();
if (board[i][j] == 2) {
board[i][j] = 0;
sx = i;
sy = j;
}
}
}
solve(board, sx, sy);
}
}
}