isFenced
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162
import java.util.ArrayList;
class Main {
public static void main(String[] args) {
show(getNeighbours(4, 2));
checkIsFenced(4, "a11c10d17a30b18c5d6a29b31c16d12", "a11");
checkIsFenced(4, "c1c5d6c10a11d12c16d17b18d19b22b23a24a29a30b31", "d17");
checkIsNotFenced(4, "c1c5d6c10a11d12c16d17b18d19b22b23a24a29a30b31", "c1c5c10c16");
checkIsNotFenced(4, "c1c5d6c10a11d12c16d17b18d19b22b23a24a29a30b31", "b18");
checkIsNotFenced(4, "c1c5d6c10a11d12c16d17b18d19b22b23a24a29a30b31", "a24a29a30");
checkIsFenced(4, "c5d6c10d12c16d17b18b19c22b26c28a29a30b31a33d34a35", "d34");
checkIsNotFenced(4, "c5d6c10d12c16d17b18b19c22b26c28a29a30b31a33d34a35", "a29a30a33a35");
checkIsNotFenced(4, "c5d6c10d12c16d17b18b19c22b26c28a29a30b31a33d34a35", "d17");
checkIsFenced(5, "a20c22d14a13b21c30d15a28b29c38d7a12b23c31d16a36b32c40d24a46b39c41d6a48b47c37d33", "b21b29");
checkIsFenced(5, "a20c22d14a13b21c30d15a28b29c38d7a12b23c31d16a36b32c40d24a46b39c41d6a48b47c37d33", "b23b32");
checkIsNotFenced(5, "a11d12d13c18a19c20a26b27b28", "c20");
checkIsNotFenced(5, "a20c22d14a13b21c30d15a28b29c38d7a12b23c31d16a36b32c40d24a46b39c41d6a48b47c37d33", "a12a13a20a28a36");
checkIsFenced(5, "a11d12d13c18a19c20a26b27b28", "c18");
checkIsFenced(5, "d0a5a6d11a12d18c19a20b26c27b28c35b36", "d11d18");
checkIsNotFenced(5, "a11d12d13c18a19c20a26b27b28", "c20");
checkIsNotFenced(5, "a11d12d13c18a19c20a26b27b28", "a11a19");
checkIsNotFenced(5, "d0a5a6d11a12d18c19a20b26c27b28c35b36", "c19c27c35");
checkIsNotFenced(5, "d0a5a6d11a12d18c19a20b26c27b28c35b36", "a5a6a12a20");
}
static void checkIsFenced(int l, String board, String bloom) {
if (!isFenced(l, board, bloom)) {
System.out.printf("should true: %d %s %s\n", l, board, bloom);
}
}
static void checkIsNotFenced(int l, String board, String bloom) {
if (isFenced(l, board, bloom)) {
System.out.printf("should false: %d %s %s\n", l, board, bloom);
}
}
static boolean isFenced(int l, String board, String bloom) {
String[] nsa = board.split("[a-d]");
String[] csa = board.split("\\d+");
ArrayList<String> cs = new ArrayList<String>();
ArrayList<Integer> ns = new ArrayList<Integer>();
for (int i = 0; i < csa.length; ++i) {
cs.add(csa[i]);
ns.add(Integer.parseInt(nsa[i + 1]));
}
String bc = bloom.substring(0, 1);
String[] bna = bloom.split("[a-d]");
ArrayList<Integer> bns = new ArrayList<Integer>();
for (int i = 1; i < bna.length; ++i) {
bns.add(Integer.parseInt(bna[i]));
}
// build map
int[][] map = new int[l * 2 - 1][l * 2 - 1];
String[][] cmap = new String[l * 2 - 1][l * 2 - 1];
int s = 0, e = l, c = 0, i = 0, j = 0;
for (i = 0; i < l * 2 - 1; ++i) {
for (j = 0; j < l * 2 - 1; ++j) {
cmap[i][j] = ".";
if (j < s || j >= e) {
cmap[i][j] = "e";
map[i][j] = -1;
} else {
map[i][j] = c++;
if (ns.contains(map[i][j])) {
String x = cs.get(ns.indexOf(map[i][j]));
if (!x.equals(bc) || bns.contains(map[i][j])) {
cmap[i][j] = x;
}
}
}
}
if (i < l - 1) e++;
if (i >= l - 1) s++;
}
// for (i = 0; i < l * 2 - 1; ++i) {
// show(cmap[i]);
// }
ns.clear();
for (int _i : bns) {
int[] neighbours = getNeighbours(l, _i);
for (int _j : neighbours) {
if (ns.contains(_j)) continue;
ns.add(_j);
}
}
// show(ns);
boolean b = true;
for (i = 0; i < l * 2 - 1; ++i) {
for (j = 0; j < l * 2 - 1; ++j) {
if (ns.contains(map[i][j]) && !bns.contains(map[i][j])) {
// System.out.printf("(%d, %d) %s\n", i, j, cmap[i][j]);
if (cmap[i][j].equals(bc) || cmap[i][j].equals(".")) {
b = false;
break;
}
}
}
if (!b) break;
}
return b;
}
public static int[] getNeighbours(int l, int n) {
// FIXME Task 4: get the list of spaces which are neighbours to the given space
// only work for size of 4,need to fix
if (l <= 1) return new int[0];
int[][] map = new int[l * 2 - 1][l * 2 - 1];
int s = 0, e = l, c = 0, _i = -l, _j = -l, i = 0, j = 0;
for (i = 0; i < l * 2 - 1; ++i) {
for (j = 0; j < l * 2 - 1; ++j) {
if (j < s || j >= e) {
map[i][j] = -1;
} else {
if ((map[i][j] = c++) == n) {
_i = i; _j = j;
}
}
}
if (i < l - 1) e++;
if (i >= l - 1) s++;
}
ArrayList<Integer> a = new ArrayList<Integer>();
i = _i; j = _j;
for (_i = -1; _i <= 1; ++_i) {
for (_j = -1; _j <= 1; ++_j) {
if (_i + _j == 0) continue;
s = i + _i; e = j + _j;
if (0 <= s && s < l * 2 - 1 && 0 <= e && e < l * 2 - 1) {
if (map[s][e] >= 0) {
a.add(map[s][e]);
}
}
}
}
int[] b = new int[a.size()];
for (i = 0; i < a.size(); ++i)
b[i] = a.get(i);
return b;
}
static void show(String[] arr) {
System.out.print(arr.length);
for (String s : arr) {
System.out.print(" [" + s + "]");
}
System.out.println();
}
static void show(int[] arr) {
System.out.print(arr.length);
for (int s : arr) {
System.out.print(" [" + s + "]");
}
System.out.println();
}
static void show(ArrayList<Integer> arr) {
System.out.print(arr.size());
for (int s : arr) {
System.out.print(" [" + s + "]");
}
System.out.println();
}
}
Java
INFO