兄貴の伝説 - hatena edition -

ソフトウェア職人を目指してます

4.6 データ構造の応用:面積計算

これは面積のマージ部分のロジックが全然思いつかなくてダメでした。。解説を読みつつ書いたものがコレ。

#include <iostream>
#include <string>
#include <vector>
#include <stack>

using namespace std;

static const char DOWN = '\\';
static const char EVEN = '_';
static const char UP = '/';

struct AREA {
  int index;
  int area;
};

int main() {
  string data;
  cin >> data;

  stack<int> input;
  vector<AREA> answers;
  AREA current = {};
  int lastIndex = 0;
  int total = 0;
  for (int i = 0; i < data.length(); i++) {
    switch (data[i]) {
    case DOWN:
      input.push(i);
      break;
    case EVEN:
      break;
    case UP:
      if (input.empty()) {
        continue;
      }
      lastIndex = input.top();
      input.pop();
      current.area = i - lastIndex;
      current.index = lastIndex;
      total += current.area;
      while (answers.size() > 0 && answers.back().index > lastIndex) {
        current.area += answers.back().area;
        answers.pop_back();
      }
      answers.push_back(current);
      break;
    default:
      break;
    }
  }

  cout << total << endl;  
  cout << answers.size();
  for (AREA answer : answers) {
      cout << " " << answer.area;
  }  
  cout << endl;

  return 0;
}

面積のマージ条件に、標高の概念を採り入れてみたのですが、入力データと答えに相当する stack/vector を、ひとつの箱でやろうとして混乱してしまい、結局解けませんでした。一通り本書を終えた後にリベンジしたいところです。