SPOJ_MKJUMPS.java

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        SPOJ_MKJUMPS solver = new SPOJ_MKJUMPS();
        solver.solve(1, in, out);
        out.close();
    }

    static class SPOJ_MKJUMPS {
        int[][] moves = {{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2},
                {1, 2}, {2, 1}, {2, -1}, {1, -2}};
        boolean[][] board;
        boolean[][] visit;

        public void solve(int testNumber, InputReader input, PrintWriter out) {
            FastScanner in = new FastScanner(input);
            int n, test = 1;
            while ((n = in.i()) > 0) {
                int count = 0;
                int startR = -1, startC = -1;
                board = new boolean[10][10];
                for (int i = 0; i < n; ++i) {
                    int skip = in.i(), len = in.i();
                    for (int j = skip; j < len + skip; ++j) {
                        if (startR < 0) {
                            startR = i;
                            startC = j;
                        }
                        board[i][j] = true;
                        count++;
                    }
                }

                visit = new boolean[10][10];
                visit[startR][startC] = true;
                int reached = dfs(startR, startC);
                int ans = count - reached;
                if (ans == 1)
                    out.printf("Case %d, %d square can not be reached.\n", test++, ans);
                else
                    out.printf("Case %d, %d squares can not be reached.\n", test++, ans);
//            for(int []i : limit)
//                System.out.println(Arrays.toString(i));
            }
        }

        int dfs(int r, int c) {
            int reached = 0;
            for (int i = 0; i < 8; ++i) {
                int nr = r + moves[i][0];
                int nc = c + moves[i][1];
                if (reachable(nr, nc) && !visit[nr][nc]) { // not visited by all neighbors
                    visit[nr][nc] = true;
                    reached = Math.max(dfs(nr, nc), reached);
                    visit[nr][nc] = false;
                }
            }
            return reached + 1;
        }

        boolean reachable(int r, int c) {
            return (r >= 0 && r < 10 && c >= 0 && c < 10) && board[r][c];
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }

    static class FastScanner {
        InputReader in;

        public FastScanner(InputReader in) {
            this.in = in;
        }

        public int i() {
            return in.nextInt();
        }

    }
}