UOA1022 Indian Puzzle

コンテストの準備中は手を着けている余裕がなかったので、後でのんびり解いてみました。

構文解析は苦手なのでずっとチームメイトに任せていたツケが回ってきて、ずいぶんとひどいバグを量産しました。ICPC選手御用達のお手軽パーザーを参考にしたものの、面倒臭がって副作用出しまくりのコードに改変したのでデバッグもやり辛いことこの上なかったです。

汚くて恐縮ですが、コード晒し上げ。デバッグ文や関係ないincludeとかは抜いときました。

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cassert>
#include <cstring>

#define REP(i,e) for(int i=0;i<(int)(e);i++)
#define FOR(i,b,e) for(int i=(int)b;i<(int)(e);i++)
#define FORC(i,b,e,c) for(int i=(int)b;i<(int)(e)&&(c);i++)
#define ALL(c) (c).begin(), (c).end()
#define EACH(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)

using namespace std;

const int nil=1<<30;
const int N=10;

char field[N][N];
int li,lj;
int let[14];

inline int toi(char c){
  if(isdigit(c)) return c-'0';
  switch(c){
  case '+': return 10;
  case '-': return 11;
  case '*': return 12;
  case '/': return 13;
  default:  assert(false);
  }
}

const char toc[]="0123456789+-*/";

int N0(char*& p){
  if(!isdigit(*p)) return nil;
  if(*p=='0'){
    ++p;
    return (isdigit(*p) ? nil : 0);
  }

  int n=0;
  for(;isdigit(*p);++p)
    n*=10, n+=((*p)-'0');

  return n;
}

int TERM(char*& p){
  int n=N0(p);
  if(n==nil) return nil;

  for(char op;op=*p,(op=='*' || op=='/');){
    int m=N0(++p); if(m==nil) return nil;
    if(op=='/'){
      if(m && n%m==0) n/=m;
      else return nil;
    }
    else n*=m;
  }

  return n;
}
int EX(char*& p){
  int n=TERM(p);
  if(n==nil) return nil;

  for(char op;op=*p,(op=='+' || op=='-');){
    int m=TERM(++p); if(m==nil) return nil;
    if(op=='+') n+=m;
    else        n-=m;
  }

  return n;
}

bool EQ(char *str,int len){
  static char fst[N],snd[N];
  memset(fst,'\0',sizeof fst);
  memset(snd,'\0',sizeof snd);

  int e=-1;
  REP(i,len) if(str[i]=='='){ e=i; break; } assert(e!=-1);
  REP(i,e) fst[i]=str[i];
  FOR(i,e+1,len) snd[i-e-1]=str[i];

  char *pf=&(fst[0]), *ps=&(snd[0]);
  int fa=EX(pf);
  if(fa==nil) return false;
  int fb=EX(ps);

  return fa==fb;
}

bool hcheck(int ci,int cj){
  static char str[N];
  int i=0;
  for(;0<=cj&&field[ci][cj]!='#';cj--,i++)
    str[i]=field[ci][cj];
  reverse(str,str+i);
  return i<3 || EQ(str,i);
}

bool vcheck(int ci,int cj){
  static char str[N];
  int i=0;
  for(;0<=ci&&field[ci][cj]!='#';ci--,i++)
    str[i]=field[ci][cj];
  reverse(str,str+i);
  return i<3 || EQ(str,i);
}

bool check(int ci,int cj){
  if(cj+1==lj || field[ci][cj+1]=='#') 
    if(!hcheck(ci,cj)) return false;
  if(ci+1==li || field[ci+1][cj]=='#') 
    if(!vcheck(ci,cj)) return false;
  return true;
}

bool backtrack(int ci,int cj){
  if(ci==li){ return true; }

  const int ni=ci+((cj+1)/lj),nj=(cj+1)%lj;
  if(field[ci][cj]=='.'){
    REP(i,14) if(let[i]){
      let[i]--;
      field[ci][cj]=toc[i];
      if(check(ci,cj) && backtrack(ni,nj)) return true;
      field[ci][cj]='.';
      let[i]++;
    }
  }
  else {
    if(!check(ci,cj)) return false;
    return backtrack(ni,nj);
  }
  return false;
}

main(){
  while(cin >> li >> lj && li|lj){
    memset(field,'\0',sizeof field);
    memset(let,0,sizeof let);

    REP(i,li) REP(j,lj) cin >> field[i][j];

    int n;
    cin >> n;
    REP(i,n){ char c; cin >> c; let[toi(c)]++; }
    cout << (backtrack(0,0) ? "Yes" : "No") << endl;
  }
}

TLEが怖くてstringを使わないように頑張りました。思ったよりもずっと速く動いてくれたのでご機嫌です。