UVa12337 Bob’s Beautiful Balls

UVa

問題
入力のの順番で、グリッドを渦状に埋め尽くすようにボールを埋める。ただし同じ列は同じ色である必要がある。
グリッドのサイズを N*M としたとき、最大の N+M を求めよ。条件を満たす N,M が存在しない場合は -1 を出力せよ。

解法
ぐるぐる巻きを実装するだけ。次に曲がる位置までの長さを計算するより、「枠外と衝突」or「既に置いたところと衝突」のタイミングで曲がるよう実装する方がミスなく書ける。

以下のコードでは 二重ループと memset で O(N^2 * M^2) になっているように見えるが、N*M = SIZE を満たす組が限定されるので間に合う。

#include <bits/stdc++.h>

using namespace std;

int SIZE;
int ans;
int t[100][100];
string str;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)

bool invalid(int x, int y) {
  if(y-1 >= 0 && (t[y][x]|t[y-1][x]) != t[y][x]) return true;
  if(y+1 >= 0 && (t[y][x]|t[y+1][x]) != t[y][x]) return true;
  return false;
}

int solve() {
  
  int const dx[] = {1,0,-1,0};
  int const dy[] = {0,1,0,-1};
  int const INF = 999999999;
  
  ans = INF;
  REP(N,2,SIZE) {
    REP(M,2,SIZE) {
      if(N*M != SIZE) continue;
      int px = -1, py = 0, k = 0;
      int idx = 0;
      bool ok = true;
      int touch = 0;
      memset(t, 0, sizeof t);
      for(;;) {
	if(touch > 1) break;
	int nx = px+dx[k], ny = py+dy[k];
	if(nx >= M || ny >= N || nx < 0 || ny < 0) { (k+=1)%=4; continue; }
	if(t[ny][nx] != 0) { (k+=1)%=4; touch ++; continue; }

	touch = 0;
	px = nx, py = ny;
	if(str[idx] == 'B') { t[py][px] = 1; }
	if(str[idx] == 'G') { t[py][px] = 2; }
	if(str[idx] == 'W') { t[py][px] = 4; }
	
	idx++;
	
	if(invalid(px, py)) { ok = false; break; }
      }
      
      if(ok) { ans = min(ans, N+M); }
    }
  }
  
  return (ans == INF) ? -1 : ans;
}

int main() {
  
  int Tc; cin >> Tc;
  REP(Tcnt,1,Tc+1) {
    cin >> str;
    SIZE = str.size();
    cout << "Case " << Tcnt << ": " << solve() << endl;
  }
  
  return 0;
}