1

SPOJ からの次の質問を解決しようとしています。

n m 個のフィールドを含む長方形のメッシュ上に、n m 個の立方体が配置され、各フィールドに 1 つの立方体が配置されました。各立方体の底辺は 1 つのフィールドをカバーし、その表面は 1 平方インチに相当します。隣接するフィールドの直方体は互いに密着しているため、それらの間に隙間がありません。大雨が建物に降り注ぎ、一部の地域では水たまりができました。

仕事

次のようなプログラムを作成します。

  • 標準入力からチェス盤のサイズとフィールドに配置された直方体の高さを読み取ります
  • 雨の後に水たまりに集まる可能性のある最大水量を計算します
  • 結果を標準出力に書き込みます。

入力

テスト ケースの数 t は入力の最初の行にあり、その後に t 個のテスト ケースが空行で区切られて続きます。各テスト ケースの最初の行には、2 つの正の整数 1 <= n <= 100、1 <= m <= 100 が書き込まれます。それらはメッシュのサイズです。次の n 行のそれぞれに、間隔 [1..10000] の m 個の整数があります。j 行目の i 番目の数値は、チェス盤の i 列目 j 列目のフィールドに配置されたインチで与えられる直方体の高さを示します。

出力

あなたのプログラムは、構造上の水たまりに集まる可能性のある水の最大体積 (立方インチで与えられる) に等しい 1 つの整数をテスケースごとに書き込む必要があります。

Example

Sample input:
1
3 6
3 3 4 4 4 2
3 1 3 2 1 4
7 3 1 6 4 1

Sample output:
5

BFS を使用して、境界要素から水たまりに流れる水の量を追加しています (パスが見つかった場合)。しかし、水たまりが 2 つの連続した直方体のような場合は処理できません。誰かがそのケースで私を助けることができますか?

4

1 に答える 1

2

これが問題に対する私の答えです。便宜上、インデックスは (1,1) から (M,N) までと仮定します

水の流れとして想像できるように、水は高い方の立方体から低い方の直方体にしか移動できません (逆方向はありません。つまり、低い方の直方体からの水は、高い方の直方体の壁に当たって止まります)。

したがって、グラフ G = (V,E) は、V が M x N 個の頂点、つまり行列上の直方体になるように作成します。高さ (i) >= 高さ (j) および (i と j が物理的に接続されている) 場合、直方体 i(th) を直方体 j(th) に接続するエッジが接続されます (一方向のみ)。

したがって、問題は単純な BFS にすぎません。

ちなみに、この問題を解決する別のものも見つかりました。ご覧ください

http://www.spojsolutions.com/212-water-among-cubes/

于 2012-09-13T10:51:52.070 に答える