Problem 1031 : Simple GUI Application
問題概要
日本語なので本文参照。(http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1031&lang=jp)
<main>10,10,190,150<menu>20,20,70,140</menu><primary>80,20,180,140 <text>90,30,170,80</text><button>130,110,170,130</button></primary></main>
のようなタグ構造によって、画面上のウィンドウの座標および包含関係が与えられる。
点(x,y)が指定された時、その点において最も表面にあるウィンドウの名前および、そのウィンドウの「直接の子ウィンドウの数」を求めよ。
解法
タグの部分は構文解析。
eval関数が構文解析の部分で、戻り値はその文字列があらわすウィンドウの数(子になっているウィンドウは含めない)
構文解析をしたら、クリックされた点がどのウィンドウに属するかを調べるが、これは線形探索をする。
また、最も表面に近いウィンドウは、タグ構造において最後に出現するため、後ろからウィンドウを調べ、一番最初にマッチしたウィンドウを返せばよい。
ソースコード
struct S{ int x1,x2,y1,y2,c; string name; bool contain(int x,int y) { return x1<=x&&x<=x2&&y1<=y&&y<=y2; } }; S pnl[1000]; int n,m; string in; int eval(int s,int t) { if(s>=t)return 0; int id=m,bt=in.find('>',s),ns=in.find('<',bt+1); m++; pnl[id].name=in.substr(s+1,bt-s-1); string tmp=in.substr(bt+1,ns-bt-1); fr(i,tmp)if(*i==',')*i=' '; stringstream ss(tmp); ss>>pnl[id].x1>>pnl[id].y1>>pnl[id].x2>>pnl[id].y2; tmp="</"+pnl[id].name+">"; int es=in.find(tmp,bt),et=es+pnl[id].name.size()+3; a int ret=1; pnl[id].c=eval(ns,es); if(et!=t)ret+=eval(et,t); return ret; } int main() { while(cin>>n,n) { cin>>in; m=0; eval(0,in.size()); rep(i,n) { int x,y,id=m-1; cin>>x>>y; for(;id>=0;id--)if(pnl[id].contain(x,y))break; if(id<0)cout<<"OUT OF MAIN PANEL 1"<<endl; else cout<<pnl[id].name<<" "<<pnl[id].c<<endl; } } return 0; }