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;
}