/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.LinkedList;
class Location {
int x;
int y;
Location(int i, int j) {
x = i;
y = j;
}
}
class Ideone
{
final static int E = 0;
final static int B = 1;
final static int W = 2;
private static boolean isCaptured_DF(int board[][], int x, int y) {
boolean visited[][] = new boolean[board.length][board[0].length];
return isCaptured_DF(board, x, y, visited);
}
private static boolean isEmpty(int board[][], int x, int y) {
if(board[x][y] == E) return true;
return false;
}
private static boolean isBlack(int board[][], int x, int y) {
if(board[x][y] == B) return true;
return false;
}
private static boolean isWhite(int board[][], int x, int y) {
if(board[x][y] == W) return true;
return false;
}
private static boolean isCaptured_DF(int board[][], int x, int y, boolean visited[][]) {
if (isEmpty(board, x, y)) return false;
if (isWhite(board, x, y) || visited[x][y]) return true;
// mark this piece visited to break infinite recursion
visited[x][y] = true;
// left
if(y > 0 && !isCaptured_DF(board, x, y-1, visited)) return false;
// right
if(y < board[0].length-1 && !isCaptured_DF(board, x, y+1, visited)) return false;
// top
if(x > 0 && !isCaptured_DF(board, x-1, y, visited)) return false;
// down
if(x < board.length-1 && !isCaptured_DF(board, x+1, y, visited)) return false;
return true;
}
private static void addToQAndMarkVisited(LinkedList<Location> Q, boolean visited[][], int x, int y) {
Q.add(new Location(x, y));
visited[x][y] = true;
}
private static boolean isNeighborEmpty(int board[][], int x, int y, LinkedList<Location> Q, boolean visited[][]) {
if (isEmpty(board, x, y)) return true;
if (isBlack(board, x, y) && !visited[x][y]) addToQAndMarkVisited(Q, visited, x, y);
return false;
}
private static boolean isCaptured_BF(int board[][], int x, int y) {
LinkedList<Location> Q = new LinkedList<Location>();
boolean visited[][] = new boolean[board.length][board[0].length];
addToQAndMarkVisited(Q, visited, x, y);
while(!Q.isEmpty()) {
Location t = Q.remove();
// left
if(t.y > 0 && isNeighborEmpty(board, t.x, t.y-1, Q, visited)) return false;
// right
if(t.y < board[0].length-1 && isNeighborEmpty(board, t.x, t.y+1, Q, visited)) return false;
// top
if(t.x > 0 && isNeighborEmpty(board, t.x-1, t.y, Q, visited)) return false;
// down
if(t.x < board.length-1 && isNeighborEmpty(board, t.x+1, t.y, Q, visited)) return false;
}
return true;
}
public static void main
(String[] args
) { int board[][] = {
{B, B, W, W},
{W, W, B, W},
{B, W, W, B},
{W, W, B, B},
{E, B, W, B},
};
// Depth First
System.
out.
println("Depth First"); System.
out.
println("==========="); for(int i=0; i<board.length; i++)
for(int j=0; j<board[0].length; j++)
if(board[i][j] == B)
System.
out.
println(i
+ " " + j
+ " " + (isCaptured_DF
(board, i, j
) ? "Captured" : "Free"));
System.
out.
println("\nBreadth First"); System.
out.
println("============="); for(int i=0; i<board.length; i++)
for(int j=0; j<board[0].length; j++)
if(board[i][j] == B)
System.
out.
println(i
+ " " + j
+ " " + (isCaptured_BF
(board, i, j
) ? "Captured" : "Free")); }
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CmltcG9ydCBqYXZhLnV0aWwuTGlua2VkTGlzdDsKCmNsYXNzIExvY2F0aW9uIHsKICAgIGludCB4OwogICAgaW50IHk7CiAgICBMb2NhdGlvbihpbnQgaSwgaW50IGopIHsKICAgICAgICB4ID0gaTsKICAgICAgICB5ID0gajsKICAgIH0KfQoKY2xhc3MgSWRlb25lCnsKICAgIGZpbmFsIHN0YXRpYyBpbnQgRSA9IDA7CiAgICBmaW5hbCBzdGF0aWMgaW50IEIgPSAxOwogICAgZmluYWwgc3RhdGljIGludCBXID0gMjsKICAgIAogICAgcHJpdmF0ZSBzdGF0aWMgYm9vbGVhbiBpc0NhcHR1cmVkX0RGKGludCBib2FyZFtdW10sIGludCB4LCBpbnQgeSkgewogICAgICAgIGJvb2xlYW4gdmlzaXRlZFtdW10gPSBuZXcgYm9vbGVhbltib2FyZC5sZW5ndGhdW2JvYXJkWzBdLmxlbmd0aF07CiAgICAgICAgcmV0dXJuIGlzQ2FwdHVyZWRfREYoYm9hcmQsIHgsIHksIHZpc2l0ZWQpOwogICAgfQoKICAgIHByaXZhdGUgc3RhdGljIGJvb2xlYW4gaXNFbXB0eShpbnQgYm9hcmRbXVtdLCBpbnQgeCwgaW50IHkpIHsKICAgICAgICBpZihib2FyZFt4XVt5XSA9PSBFKSByZXR1cm4gdHJ1ZTsKICAgICAgICByZXR1cm4gZmFsc2U7CiAgICB9CgogICAgcHJpdmF0ZSBzdGF0aWMgYm9vbGVhbiBpc0JsYWNrKGludCBib2FyZFtdW10sIGludCB4LCBpbnQgeSkgewogICAgICAgIGlmKGJvYXJkW3hdW3ldID09IEIpIHJldHVybiB0cnVlOwogICAgICAgIHJldHVybiBmYWxzZTsKICAgIH0KICAgIAogICAgcHJpdmF0ZSBzdGF0aWMgYm9vbGVhbiBpc1doaXRlKGludCBib2FyZFtdW10sIGludCB4LCBpbnQgeSkgewogICAgICAgIGlmKGJvYXJkW3hdW3ldID09IFcpIHJldHVybiB0cnVlOwogICAgICAgIHJldHVybiBmYWxzZTsKICAgIH0KICAgIAogICAgcHJpdmF0ZSBzdGF0aWMgYm9vbGVhbiBpc0NhcHR1cmVkX0RGKGludCBib2FyZFtdW10sIGludCB4LCBpbnQgeSwgYm9vbGVhbiB2aXNpdGVkW11bXSkgewogICAgICAgIGlmIChpc0VtcHR5KGJvYXJkLCB4LCB5KSkgcmV0dXJuIGZhbHNlOwogICAgICAgIGlmIChpc1doaXRlKGJvYXJkLCB4LCB5KSB8fCB2aXNpdGVkW3hdW3ldKSByZXR1cm4gdHJ1ZTsKCiAgICAgICAgLy8gbWFyayB0aGlzIHBpZWNlIHZpc2l0ZWQgdG8gYnJlYWsgaW5maW5pdGUgcmVjdXJzaW9uCiAgICAgICAgdmlzaXRlZFt4XVt5XSA9IHRydWU7CgogICAgICAgIC8vIGxlZnQKICAgICAgICBpZih5ID4gMCAmJiAhaXNDYXB0dXJlZF9ERihib2FyZCwgeCwgeS0xLCB2aXNpdGVkKSkgcmV0dXJuIGZhbHNlOwogICAgICAgIAogICAgICAgIC8vIHJpZ2h0CiAgICAgICAgaWYoeSA8IGJvYXJkWzBdLmxlbmd0aC0xICYmICFpc0NhcHR1cmVkX0RGKGJvYXJkLCB4LCB5KzEsIHZpc2l0ZWQpKSByZXR1cm4gZmFsc2U7CiAgICAgICAgCiAgICAgICAgLy8gdG9wCiAgICAgICAgaWYoeCA+IDAgJiYgIWlzQ2FwdHVyZWRfREYoYm9hcmQsIHgtMSwgeSwgdmlzaXRlZCkpIHJldHVybiBmYWxzZTsKICAgICAgICAKICAgICAgICAvLyBkb3duCiAgICAgICAgaWYoeCA8IGJvYXJkLmxlbmd0aC0xICYmICFpc0NhcHR1cmVkX0RGKGJvYXJkLCB4KzEsIHksIHZpc2l0ZWQpKSByZXR1cm4gZmFsc2U7CgogICAgICAgIHJldHVybiB0cnVlOwogICAgfQoKICAgIHByaXZhdGUgc3RhdGljIHZvaWQgYWRkVG9RQW5kTWFya1Zpc2l0ZWQoTGlua2VkTGlzdDxMb2NhdGlvbj4gUSwgYm9vbGVhbiB2aXNpdGVkW11bXSwgaW50IHgsIGludCB5KSB7CiAgICAgICAgUS5hZGQobmV3IExvY2F0aW9uKHgsIHkpKTsKICAgICAgICB2aXNpdGVkW3hdW3ldID0gdHJ1ZTsgICAgICAgIAogICAgfQogICAgCiAgICBwcml2YXRlIHN0YXRpYyBib29sZWFuIGlzTmVpZ2hib3JFbXB0eShpbnQgYm9hcmRbXVtdLCBpbnQgeCwgaW50IHksIExpbmtlZExpc3Q8TG9jYXRpb24+IFEsIGJvb2xlYW4gdmlzaXRlZFtdW10pIHsKICAgICAgICBpZiAoaXNFbXB0eShib2FyZCwgeCwgeSkpIHJldHVybiB0cnVlOwogICAgICAgIGlmIChpc0JsYWNrKGJvYXJkLCB4LCB5KSAmJiAhdmlzaXRlZFt4XVt5XSkgYWRkVG9RQW5kTWFya1Zpc2l0ZWQoUSwgdmlzaXRlZCwgeCwgeSk7CiAgICAgICAgcmV0dXJuIGZhbHNlOwogICAgICAgIAogICAgfQogICAgcHJpdmF0ZSBzdGF0aWMgYm9vbGVhbiBpc0NhcHR1cmVkX0JGKGludCBib2FyZFtdW10sIGludCB4LCBpbnQgeSkgewogICAgICAgIExpbmtlZExpc3Q8TG9jYXRpb24+IFEgPSBuZXcgTGlua2VkTGlzdDxMb2NhdGlvbj4oKTsKICAgICAgICBib29sZWFuIHZpc2l0ZWRbXVtdID0gbmV3IGJvb2xlYW5bYm9hcmQubGVuZ3RoXVtib2FyZFswXS5sZW5ndGhdOwogICAgICAgIAogICAgICAgIGFkZFRvUUFuZE1hcmtWaXNpdGVkKFEsIHZpc2l0ZWQsIHgsIHkpOwogICAgICAgIAogICAgICAgIHdoaWxlKCFRLmlzRW1wdHkoKSkgewogICAgICAgICAgICBMb2NhdGlvbiB0ID0gUS5yZW1vdmUoKTsKICAgICAgICAgICAgCiAgICAgICAgICAgIC8vIGxlZnQKICAgICAgICAgICAgaWYodC55ID4gMCAmJiBpc05laWdoYm9yRW1wdHkoYm9hcmQsIHQueCwgdC55LTEsIFEsIHZpc2l0ZWQpKSByZXR1cm4gZmFsc2U7IAogICAgICAgICAgICAKICAgICAgICAgICAgLy8gcmlnaHQKICAgICAgICAgICAgaWYodC55IDwgYm9hcmRbMF0ubGVuZ3RoLTEgJiYgaXNOZWlnaGJvckVtcHR5KGJvYXJkLCB0LngsIHQueSsxLCBRLCB2aXNpdGVkKSkgcmV0dXJuIGZhbHNlOwoKICAgICAgICAgICAgLy8gdG9wCiAgICAgICAgICAgIGlmKHQueCA+IDAgJiYgaXNOZWlnaGJvckVtcHR5KGJvYXJkLCB0LngtMSwgdC55LCBRLCB2aXNpdGVkKSkgcmV0dXJuIGZhbHNlOwoKICAgICAgICAgICAgLy8gZG93bgogICAgICAgICAgICBpZih0LnggPCBib2FyZC5sZW5ndGgtMSAmJiBpc05laWdoYm9yRW1wdHkoYm9hcmQsIHQueCsxLCB0LnksIFEsIHZpc2l0ZWQpKSByZXR1cm4gZmFsc2U7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIHJldHVybiB0cnVlOwogICAgfQoKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgICAgICBpbnQgYm9hcmRbXVtdID0gewogICAgICAgICAgICAgICAgICAgICAgICAgICAge0IsIEIsIFcsIFd9LAogICAgICAgICAgICAgICAgICAgICAgICAgICAge1csIFcsIEIsIFd9LAogICAgICAgICAgICAgICAgICAgICAgICAgICAge0IsIFcsIFcsIEJ9LAogICAgICAgICAgICAgICAgICAgICAgICAgICAge1csIFcsIEIsIEJ9LCAgICAgICAgICAgICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHtFLCBCLCBXLCBCfSwKICAgICAgICAgICAgICAgICAgICAgICAgfTsKCiAgICAgICAgLy8gRGVwdGggRmlyc3QKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIkRlcHRoIEZpcnN0Iik7CiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCI9PT09PT09PT09PSIpOyAgICAgICAgCiAgICAgICAgZm9yKGludCBpPTA7IGk8Ym9hcmQubGVuZ3RoOyBpKyspCiAgICAgICAgICAgIGZvcihpbnQgaj0wOyBqPGJvYXJkWzBdLmxlbmd0aDsgaisrKQogICAgICAgICAgICAgICAgaWYoYm9hcmRbaV1bal0gPT0gQikKICAgICAgICAgICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oaSArICIgIiArIGogKyAiICIgKyAoaXNDYXB0dXJlZF9ERihib2FyZCwgaSwgaikgPyAiQ2FwdHVyZWQiIDogIkZyZWUiKSk7CiAgICAgICAgCiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJcbkJyZWFkdGggRmlyc3QiKTsKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIj09PT09PT09PT09PT0iKTsgICAgICAgICAgICAKICAgICAgICBmb3IoaW50IGk9MDsgaTxib2FyZC5sZW5ndGg7IGkrKykKICAgICAgICAgICAgZm9yKGludCBqPTA7IGo8Ym9hcmRbMF0ubGVuZ3RoOyBqKyspCiAgICAgICAgICAgICAgICBpZihib2FyZFtpXVtqXSA9PSBCKQogICAgICAgICAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbihpICsgIiAiICsgaiArICIgIiArIChpc0NhcHR1cmVkX0JGKGJvYXJkLCBpLCBqKSA/ICJDYXB0dXJlZCIgOiAiRnJlZSIpKTsKICAgIH0KfQo=