PKU 3923 Ugly Windows
http://poj.org/problem?id=3923
一番前面にあるウィンドウを答えるというような問題。
ウィンドウの端っこをなぞっていく方針だとWA。
ウィンドウの中にウィンドウがあるという場合を考慮してもWA。
何も無いところを幅優先して、一種類のフレームにしかぶつからなかったらそれは最前面にあるとしたらACになりました。何が原因でWAになったのかよくわかりません。
while(q.empty())としてて少しだけはまりました。
string in[100]; bool vis[100][100]; main(){ int n,m; while(cin>>n>>m,n|m){ memset(vis,0,sizeof(vis)); rep(i,n)cin>>in[i]; set<char> ans; rep(i,n){ rep(j,m){ if(vis[i][j] || in[i][j]!='.')continue; set<char> app; queue<PI> q; q.push(mp(i,j)); while(!q.empty()){ int cx=q.front().F,cy=q.front().S; q.pop(); if(vis[cx][cy])continue; vis[cx][cy]=true; rep(k,4){ int nx=cx+dx[k],ny=cy+dy[k]; if(nx<0 || n<=nx || ny<0 || m<=ny || vis[nx][ny])continue; if(in[nx][ny]=='.')q.push(mp(nx,ny)); else app.insert(in[nx][ny]); } } if(app.size()==1)ans.insert(*app.begin()); } } FOR(siter,ans)cout<<*siter; cout<<endl; } }