目次
2次元世界の水たまり(難易度:★★★☆☆)
問題
2次元世界での地面の高さ(1~9)が、’1’~’9′ の文字列で与えられる時、上空から雨が充分降ったときにその部分に貯まる水の面積を返す関数 int areaOfThePods(const string& str) を実装しなさい。
なお、高さが指定された部分の左右の地面高はマイナス無限大であるものとし、左右の端から水が溢れるものとする。 また、引数文字列中に ‘1’~’9′ 以外の文字が含まれていた場合は -1 を返すものとする。
例えば、引数に “3141592653” が与えられた場合の地形は下図のようになる。
ここに上空から充分な雨が降ると、下図の “○” 部分に水が貯まるので、貯まる水の面積は9となる。
#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++ライブラリ入門 連載目次リンク
![]() |
筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。 |