UVa183 Bit Maps
分類:adhoc
n*mの01画像が与えられるので指定の形式にエンコードする。もしくはエンコード結果が与えられるので画像を復元する。再帰関数を二つ書いて終わり。
#include <iostream> using namespace std; char bitmap[200][200]; int lnum; void rec(int rs, int re, int cs, int ce) { int sum = 0; for (int i = rs; i < re; i++) { for (int j = cs; j < ce; j++) { sum += bitmap[i][j] - '0'; } } if (sum == 0) { if (lnum++ == 50) { lnum = 1; cout << endl; } cout << 0; } else if (sum == (re - rs) * (ce - cs)) { if (lnum++ == 50) { lnum = 1; cout << endl; } cout << 1; } else { if (lnum++ == 50) { lnum = 1; cout << endl; } cout << 'D'; if (re - rs == 1) { int cm = (cs + ce) / 2; if ((ce - cs) % 2) cm++; rec(rs, re, cs, cm); rec(rs, re, cm, ce); } else if (ce - cs == 1) { int rm = (rs + re) / 2; if ((re - rs) % 2) rm++; rec(rs, rm, cs, ce); rec(rm, re, cs, ce); } else { int cm = (cs + ce) / 2; if ((ce - cs) % 2) cm++; int rm = (rs + re) / 2; if ((re - rs) % 2) rm++; rec(rs, rm, cs, cm); rec(rs, rm, cm, ce); rec(rm, re, cs, cm); rec(rm, re, cm, ce); } } } int rrec(int rs, int re, int cs, int ce, string &s, int p) { if (isdigit(s[p])) { for (int i = rs; i < re; i++) { for (int j = cs; j < ce; j++) { bitmap[i][j] = s[p]; } } return p + 1; } else { p++; if (re - rs == 1) { int cm = (cs + ce) / 2; if ((ce - cs) % 2) cm++; p = rrec(rs, re, cs, cm, s, p); p = rrec(rs, re, cm, ce, s, p); return p; } else if (ce - cs == 1) { int rm = (rs + re) / 2; if ((re - rs) % 2) rm++; p = rrec(rs, rm, cs, ce, s, p); p = rrec(rm, re, cs, ce, s, p); return p; } else { int cm = (cs + ce) / 2; if ((ce - cs) % 2) cm++; int rm = (rs + re) / 2; if ((re - rs) % 2) rm++; p = rrec(rs, rm, cs, cm, s, p); p = rrec(rs, rm, cm, ce, s, p); p = rrec(rm, re, cs, cm, s, p); p = rrec(rm, re, cm, ce, s, p); return p; } } } main () { char format; while (cin >> format, format != '#') { int row, col; cin >> row >> col; lnum = 0; if (format == 'B') { for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { cin >> bitmap[i][j]; } } printf("D%4d%4d\n", row, col); if (row > 0 && col > 0) rec(0, row, 0, col); cout << endl; } else if (format == 'D') { string line; getline(cin, line); getline(cin, line); printf("B%4d%4d\n", row, col); rrec(0, row, 0, col, line, 0); for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (lnum++ == 50) { lnum = 1; cout << endl; } cout << bitmap[i][j]; } } cout << endl; } } }