ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1031 Simple GUI Application

・概要
問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1031


・解法
構文解析です。

親のタグから子のタグへと再帰的に探索をかけることで、どのタグが選ばれたのかを出力させることができます。


ソースコード

#include<iostream>
#include<string>
#include<vector>
#include<cctype>
using namespace std;

struct Panel{
  int x1,y1,x2,y2;
  string name;
  vector<Panel> child;
	 
  Panel(){child.clear();}
  Panel(int x1, int y1, int x2, int y2, string n, vector<Panel> c):
    x1(x1),y1(y1),x2(x2),y2(y2),name(n),child(c){}
};

int pos;
string s;
Panel panel;


void end_tag(){
  while(s[pos++]!='>');
}


string tag_name(){
  string res = "";
  while(true){
    if(s[pos]=='>')return res;
    else res += s[pos++];
  }
}


int tag_val(){
	int val = 0;
  while(isdigit(s[pos])){
    val = 10*val + (int)(s[pos] - '0');
    pos++;
  }
  if(s[pos]==',')pos++;
  return val;
}


Panel start_tag(){
  int x1,y1,x2,y2;
  string name = "";
  vector<Panel> child;
	 
  if(s[pos]=='<'){
    pos++;
    name = tag_name();
    pos++;
  }
  if(isdigit(s[pos])){
    x1 = tag_val();
    y1 = tag_val();
    x2 = tag_val();
    y2 = tag_val();
  }
  while(!(s[pos]=='<' && s[pos+1]=='/')){
    child.push_back(start_tag());
  }
  if(s[pos]=='<' && s[pos+1]=='/'){
    end_tag();
    return Panel(x1,y1,x2,y2,name,child);
  }
	 
  return Panel();
}


Panel touch(Panel panel, int x, int y){
  Panel res = panel;
  for(int i = 0 ; i < panel.child.size() ; i++){
    Panel p = panel.child[i];
    if(p.x1 <= x && x <= p.x2 && p.y1 <= y && y <= p.y2){
      res = touch(panel.child[i], x, y);
    }
  }
  return res;
}


int main(){
  int n;
  while(cin >> n){
    if(n==0)break;
    cin >> s;
    pos = 0;
    panel = start_tag();
    for(int i = 0 ; i < n ; i++){
      int x,y;
      cin >> x >> y;
      if(panel.x1 <= x && x <= panel.x2 && panel.y1 <= y && y <= panel.y2){
        Panel ans = touch(panel, x, y);
        cout << ans.name << " " << ans.child.size() << endl;
      }
      else{
        cout << "OUT OF MAIN PANEL 1" << endl;
      }
    }
  }
  return 0;
}