Skip to content

Instantly share code, notes, and snippets.

@hiroshi-cl
Created June 25, 2013 06:46
Show Gist options
  • Save hiroshi-cl/5856482 to your computer and use it in GitHub Desktop.
Save hiroshi-cl/5856482 to your computer and use it in GitHub Desktop.
ACM-ICPC 模擬地区予選 2012 G: Ancient Commemorative Monolith [Licence: NYSL Version 0.9982]
import java.util.*;
public class Main {
private static final Scanner sc = new Scanner(System.in);
public static void main(String... args) throws Exception {
while (sc.hasNext()) {
final int n = sc.nextInt();
final int m = sc.nextInt();
if (n == 0 && m == 0)
return;
solve(n, m);
}
}
private static void solve(final int n, final int m) {
final Map<Bitmap, Character> gs = new HashMap<Bitmap, Character>();
final Map<Bitmap, Character> rs = new HashMap<Bitmap, Character>();
int max = 0;
for (int i = 0; i < n; i++) {
final char c = sc.next().charAt(0);
final int h = sc.nextInt();
final int w = sc.nextInt();
final char[][] cs = new char[h][];
for (int j = 0; j < h; j++)
cs[j] = sc.next().toCharArray();
{
final BitSet[] bitmap = new BitSet[w];
for (int j = 0; j < w; j++)
bitmap[j] = new BitSet();
for (int j = 0; j < h; j++)
for (int k = 0; k < w; k++)
bitmap[k].set(j, cs[j][k] == '*');
final Bitmap bm = new Bitmap(h, w, bitmap);
if (gs.containsKey(bm))
throw null;
gs.put(bm, c);
}
{
final BitSet[] reverse = new BitSet[w];
for (int j = 0; j < w; j++)
reverse[j] = new BitSet();
for (int j = 0; j < h; j++)
for (int k = 0; k < w; k++)
reverse[k].set(j, cs[j][w - k - 1] == '*');
final Bitmap bm = new Bitmap(h, w, reverse);
if (rs.containsKey(bm))
throw null;
rs.put(bm, c);
}
max = Math.max(max, h);
}
for (int i = 0; i < m; i++) {
final int h = sc.nextInt();
final int w = sc.nextInt();
final char[][] cs = new char[h][];
for (int j = 0; j < h; j++)
cs[j] = sc.next().toCharArray();
final BitSet[] bitmap = new BitSet[w + 1];
for (int j = 0; j <= w; j++)
bitmap[j] = new BitSet();
for (int j = 0; j < h; j++)
for (int k = 0; k < w; k++)
bitmap[k].set(j + 1, cs[j][k] == '*');
System.out.println(match(gs, rs, h + 2, w + 1, bitmap, max));
}
System.out.println("#");
}
public static CharSequence match(final Map<Bitmap, Character> gs, final Map<Bitmap, Character> rs, final int h,
final int w, final BitSet[] program, final int th) {
return new PatternMatcher(gs, rs, program, w, th).match(0, h);
}
private static class PatternMatcher {
public final Map<Bitmap, Character> gs, rs;
public final BitSet[] program;
public final int end;
public final int th;
private int cur = 0;
public PatternMatcher(Map<Bitmap, Character> gs, Map<Bitmap, Character> rs, BitSet[] program, int end, int th) {
this.gs = gs;
this.rs = rs;
this.program = program;
this.end = end;
this.th = th;
}
public CharSequence match(final int lo, final int up) {
final StringBuilder l2r = new StringBuilder();
final StringBuilder r2l = new StringBuilder();
final Deque<CharSequence> loops = new ArrayDeque<CharSequence>();
// debug(lo, up);
while (cur < end) {
int min = -1;
int max = 0;
for (int i = lo; i < up; i++)
if (program[cur].get(i)) {
if (min < 0)
min = i;
max = i + 1;
}
if (min < 0)
;
else if (max - min == up - lo) {
cur++;
break;
} else if (max - min > th) {
// debug("frame", min, max);
// frame
l2r.append('@');
r2l.append('@');
cur++;
loops.offerLast("[" + match(min + 1, max - 1) + "]");
} else {
// glyph
int r = cur + 1;
int miny = min, maxy = max;
for (; program[r].get(lo, up).cardinality() > 0; r++) {
for (int i = lo; i < miny; i++)
if (program[r].get(i)) {
miny = i;
break;
}
for (int i = up - 1; i >= maxy; i--)
if (program[r].get(i)) {
maxy = i + 1;
break;
}
}
final int h = maxy - miny;
final int w = r - cur;
final BitSet[] bitmap = new BitSet[w];
for (int i = 0; i < w; i++)
bitmap[i] = program[i + cur].get(miny, maxy);
final Bitmap bm = new Bitmap(h, w, bitmap);
l2r.append(gs.containsKey(bm) ? gs.get(bm) : '_');
r2l.append(rs.containsKey(bm) ? rs.get(bm) : '_');
// for (int i = 0; i < h; i++) {
// final StringBuilder sb = new StringBuilder();
// for (int j = 0; j < w; j++)
// sb.append(program[cur + j].get(miny + i) ? '*' : '.');
// debug(sb);
// }
cur = r;
}
cur++;
}
// debug(lo, up, l2r, r2l, loops);
if (l2r.indexOf("_") < 0) {
final StringBuilder sb = new StringBuilder();
for (final char c : l2r.toString().toCharArray())
sb.append(c == '@' ? loops.pollFirst() : c);
return sb;
} else if (r2l.indexOf("_") < 0) {
final StringBuilder sb = new StringBuilder();
for (final char c : r2l.reverse().toString().toCharArray())
sb.append(c == '@' ? loops.pollLast() : c);
return sb;
} else
throw null;
}
}
public static class Bitmap {
public final int h, w;
public final BitSet[] bitmap;
public Bitmap(int h, int w, BitSet[] bitmap) {
this.h = h;
this.w = w;
this.bitmap = bitmap;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + Arrays.hashCode(bitmap);
result = prime * result + h;
result = prime * result + w;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (!(obj instanceof Bitmap))
return false;
Bitmap other = (Bitmap) obj;
if (!Arrays.deepEquals(bitmap, other.bitmap))
return false;
if (h != other.h)
return false;
if (w != other.w)
return false;
return true;
}
}
private static void debug(Object... os) {
System.err.println(Arrays.deepToString(os));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment