競技プログラミング風 C++問題集【第4回】


目次

2次元世界の水たまり(難易度:★★★☆☆)

問題

2次元世界での地面の高さ(1~9)が、’1’~’9′ の文字列で与えられる時、上空から雨が充分降ったときにその部分に貯まる水の面積を返す関数 int areaOfThePods(const string& str) を実装しなさい。

なお、高さが指定された部分の左右の地面高はマイナス無限大であるものとし、左右の端から水が溢れるものとする。 また、引数文字列中に ‘1’~’9′ 以外の文字が含まれていた場合は -1 を返すものとする。

例えば、引数に “3141592653” が与えられた場合の地形は下図のようになる。

競技プログラミング風C++問題集【第4回】_01

ここに上空から充分な雨が降ると、下図の “○” 部分に水が貯まるので、貯まる水の面積は9となる。

競技プログラミング風C++問題集【第4回】_02

#include <iostream>       //  標準入出力ライブラリ
#include <string>
#include <vector>
#include <deque>
#include <unordered_set>
using namespace std;    //  std 名前空間使用
#define DO_TEST(exp)    do_test(exp, __LINE__)
void do_test(bool b, int line) {
    if( b ) return;     //  OK
    cout << "\nNG at line " << line << "\n";
    exit(1);
}
int areaOfThePods(const string& str) {
    //  ToDo: ここに str で指定された地形に貯まる水の面積を返すコードを記述
    return 0;
}
int main() {
    DO_TEST( areaOfThePods("1234565432") == 0 );
    DO_TEST( areaOfThePods("5432123456") == 16 );
    DO_TEST( areaOfThePods("5432123456") == 16 );
    DO_TEST( areaOfThePods("3141592653") == 9 );
    DO_TEST( areaOfThePods("3121592653") == 9 );
    cout << "\nGood Job!\n";
    return 0;
}
ヒント
解答例
解説

関連記事

競技プログラミング風 C++問題集【第4回】

目次 2次元世界の水たまり(難易度:★★★☆☆) 2次元世界の水たまり(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席) […]
コメントなし

競技プログラミング風 C++問題集【第3回】

目次 双方向リンクリスト(難易度:★★★☆☆) 双方向リンクリスト(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。v […]
コメントなし

競技プログラミング風 C++問題集【第2回】

目次 ‘1’~’3’を’a’~’c’に置換(難易度:★★☆☆☆) 逆ポーランド記法(難易度:★★★☆☆) ‘1& […]
コメントなし

競技プログラミング風 C++問題集【第1回】

はじめに 今回から4回にわたって「競技プログラミング風 C++問題集」をお届けする。 出題形式は以前の「競技プログラミング風 標準C++ライブラリ入門」と同じだ。 各問題は、「問題文」「テストコード」「ヒント」「解答例」 […]
コメントなし
筆者:津田伸秀
プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。
  • このエントリーをはてなブックマークに追加

PAGE TOP