鞍点

説明

ここでの課題は、ツリーハウスを建てられそうな木を見つけることです。

データ会社は、木の高さを表すグリッドとしてデータを提供してくれます。グリッドの行は東西方向を、列は南北方向を表します。

条件を満たす木は、その行の中で最も大きく、かつその列の中で最も小さい木です。

グリッドによっては、条件を満たす木が1本もないこともあります。1本だけのこともあれば、何本もあることもあります。

次は、候補となる木がちょうど1本だけあるグリッドです。

1  2  3  4

|----------- 1 | 9 8 7 8 2 | 5 3 2 4 <--- potential tree house at row 2, column 1, for tree with height 5 3 | 6 6 7 1

• 2行目の値は5、3、1です。最も大きい値は5です。
• 1列目の値は9、5、6です。最も小さい値は5です。

つまり、[2, 1]（行2、列1）の地点は、ツリーハウスにうってつけの場所です。

---

出典

J DalbeyのProgramming Practiceの問題集