Skip to content

Instantly share code, notes, and snippets.

@mt40
Created March 24, 2016 15:10
Show Gist options
  • Save mt40/5a222b2dc56b9067ca61 to your computer and use it in GitHub Desktop.
Save mt40/5a222b2dc56b9067ca61 to your computer and use it in GitHub Desktop.
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();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment