PKU 2361 Tic Tac Toe
http://poj.org/problem?id=2361
tic tac toeというゲームの盤面が与えられる。
この盤面が、ゲームの終了状態または、途中の状態としてありうるかを判定するという問題。
似たような問題がありましたよね。
PKU3075でした。
set<string> app; bool ok(const string&in){ bool ret=false; rep(i,3){ ret|=in[i*3]!='.'&&in[i*3]==in[i*3+1]&&in[i*3+1]==in[i*3+2]; ret|=in[i]!='.'&&in[i]==in[i+3]&&in[i+3]==in[i+6]; } ret|=in[0]!='.'&&in[0]==in[4]&&in[0]==in[8]; ret|=in[2]!='.'&&in[2]==in[4]&&in[4]==in[6]; return ret; } main(){ queue<pair<int,string> >q; q.push(mp(0,".........")); while(!q.empty()){ int c=q.front().F; string st=q.front().S; q.pop(); if(app.count(st))continue; app.insert(st); if(ok(st))continue; rep(i,9){ if(st[i]!='.')continue; if(c&1)st[i]='O'; else st[i]='X'; if(!app.count(st))q.push(mp(c+1,st)); st[i]='.'; } } int n; cin>>n; while(n--){ string temp,in; rep(i,3){ cin>>temp; in+=temp; } cout<<(app.count(in)?"yes":"no")<<endl; } }