Problem A - Elegant Diamond

問題

以下のように数字(0〜9)を並べたものを「ダイアモンド」という．

   2       8      3     7
  3 3     3 8    2 2
 4 1 4     8      1
  3 3 
   2

与えられたダイアモンドに対して 0 個以上の数字を追加することで，全体を上下対称かつ左右対称なダイアモンドにしたい．最小でいくつの数字を追加する必要があるか？

考え方

まず入力について．変に形を変更しない方がいい．つまり入力が

  2
 3 3
4 1 4
 3 3 
  2

なら

string diamond[] = {"  2  ", " 3 3 ", "4 1 4", " 3 3 ", "  2  "};

という感じがオススメ．この形で考えると，対称軸が各文字の所になるのである．

次に対称軸を探索する範囲を探る．単純に考えて，元々のダイアモンドが条件を満たしていれば対称軸は中央である．逆に全部の数字がバラバラの場合，[0][0], [0][n-1], [n-1][0], [n-1][n-1] 辺りが対称軸になる．
なので diamond[] で確保されている範囲だけ探索すれば十分．対称になっているかどうかのチェックを行う際には元々置かれている数字が対称になっているかだけで十分．計算量的に O(n⁴) だけど n≦101 だから大丈夫．
最後に，対称軸が (x, y) だったとき，ダイアモンドのサイズは |x - k| + |y - k| + k になる（テキトウに考察して下さいな．）ので，出力数は (|x - k| + |y - k| + k)² - k² になる．

コード

#include <string>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int input(vector<string>& dia)
{
  int k;
  cin >> k;
  int n = 2 * k - 1;
  dia.resize(n);
  getline(cin, dia[0]);
  for( int i = 0 ; i < n ; ++i ) {
    getline(cin, dia[i]);
    dia[i].resize(n, ' ');
  }
  return k;
}

bool isMirror(vector<string>& dia, int n, int r, int c)
{
  for( int i = 0 ; i < n ; ++i ) {
    for( int x0 = c - 1, x1 = c + 1 ; x0 >= 0 && x1 < n ; --x0, ++x1 ) {
      char c0 = dia[i][x0], c1 = dia[i][x1];
      if( c0 != ' ' && c1 != ' ' && c0 != c1 ) return false;
    }
    for( int y0 = r - 1, y1 = r + 1 ; y0 >= 0 && y1 < n ; --y0, ++y1 ) {
      char c0 = dia[y0][i], c1 = dia[y1][i];
      if( c0 != ' ' && c1 != ' ' && c0 != c1 ) return false;
    }
  }
  return true;
}

int getSize(int k, vector<string>& dia)
{
  int n = 2 * k - 1;
  int sz = n;
  for( int r = 0 ; r < n ; ++r ) {
    for( int c = 0 ; c < n ; ++c ) {
      int d = abs(r-k+1) + abs(c-k+1);
      if( sz > d && isMirror(dia, n, r, c) ) sz = d;
    }
  }
  return sz + k;
}

int solve(void)
{
  vector<string> dia;
  int k = input(dia);
  int sz = getSize(k, dia);
  return sz*sz - k*k;
}

int main(void)
{
  int T;
  cin >> T;
  for( int t = 1 ; t <= T ; ++t ) {
    cerr << "Case #" << t << "\n";
    cout << "Case #" << t << ": " << solve() << "\n";
  }
  return 0;
}