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を使わないように頑張りました。思ったよりもずっと速く動いてくれたのでご機嫌です。