UVa1103

UVa1103

やるだけ

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <sstream>

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)

#define VAR(a) cout << #a << " : " << a << endl;

typedef long long int lli;

using namespace std;

const int H = 200 + 10;
const int W = 200 + 10;
int color[H][W];

int conv(char c)
{
  static const string s = "0123456789abcdef";
  return s.find(c);
}

void show(void)
{
  for (int i = 0; i < (int)30; ++i) {
    for (int j = 0; j < (int)84; ++j) {
      if (color[i][j] == -1) cout << '@';
      else if (color[i][j] == 1) cout << 1 ;
      else cout << (char)('A' + color[i][j] - 2);
    }
    cout << endl;
  }
  cout << endl;
  return ;
}

const int di[] = {0, 0, -1, +1};
const int dj[] = {-1, +1, 0, 0};

int h, w;

void rec(int i, int j, int n, int m)
{
  color[i][j] = m;

  for (int d = 0; d < (int)4; ++d) {
    int ni = i + di[d];
    int nj = j + dj[d];
    if (ni < 0 || nj < 0) continue;
    if (H <= ni || W <= nj) continue;
    if (color[ni][nj] != n) continue;
    rec(ni, nj, n, m);
  }

  return ;
}

int main(int argc, char *argv[])
{
  while (cin >> h >> w && (h | w)) {
   
    fill(&color[0][0], &color[H - 1][W], 0);

    for (int i = 0; i < (int)h; ++i) {
      int k = 0;
      for (int j = 0; j < (int)w; ++j) {
        char c;
        cin >> c;
        int n = conv(c);
        for (int m = 3; 0 <= m; --m) {
          color[i + 1][k++ + 1] = (bool)(n & (1 << m));
        }
      }
    }
    w *= 4;
    ++w;
    ++h;
   
    rec(0, 0, color[0][0], -1);

    int cnt = 2;
    for (int i = 0; i < (int)H; ++i) {
      for (int j = 0; j < (int)W; ++j) {
        if (color[i][j] == 0) {
          rec(i, j, color[i][j], cnt++);
        }
      }
    }

    vector<int> v;
    for (int i = 0; i < (int)H; ++i) {
      for (int j = 0; j < (int)W; ++j) {
        if (color[i][j] != 1) continue;
        queue< pair<int, int> > q;
        set<int> s;
        color[i][j] = -2;
        for (q.push(make_pair(i, j)); q.size(); q.pop()) {
          for (int d = 0; d < (int)4; ++d) {
            int ni = q.front().first + di[d];
            int nj = q.front().second + dj[d];
            if (ni < 0 || nj < 0) continue;
            if (H <= ni || W <= nj) continue;
            if (2 <= color[ni][nj]) s.insert(color[ni][nj]);
            if (color[ni][nj] != 1) continue;           
            color[ni][nj] = -2;
            q.push(make_pair(ni, nj));
          }
        }
        v.push_back(s.size());
      }
    }

    const string C = "WAKJSD";
    string s;
    for (int i = 0; i < (int)v.size(); ++i) {
      s += C[v[i]];
    }   
    sort(s.begin(), s.end());

    static int tc = 0;
    cout << "Case " << ++tc << ": " << s << endl;
  }
  return 0;
}