0

コンソールからいくつかのオブジェクトを読み取る必要があります。これは、C で書かれた戦艦ゲームに少し似ています。考えてみてください。私は 6x6 配列のプラットフォームを持っています。ユーザーからのユーザー入力を取得しています。文字 'X' は、それがユーザーが入力を与えた後の配列の例は次のとおりです。

0,0                       0,6      

  X              XXX
 X                X  
   XX             X 
     X




6,0                       6,6

申し訳ありませんが、出力が明確ではありません。ユーザーが入力した X 文字の出力です。2 つのグループの「x」文字は結合されているため、グラフには 2 つのオブジェクトがあります。グループ。X 文字の方向を対称にすることはできません。結合された x 文字のグループが存在する可能性があり、グループを数えたいと考えています。

4

1 に答える 1

1

問題をグラフとしてモデル化します (既に理解しているようにG=(V,E)) :VxE = { (u,v) | there is X in both u and v }

解析中に、すべての座標をコンテナーに保存し、それぞれを訪問したかどうかを示すブール値にマップします。

ここで、まだ訪問されていない x がある間繰り返します: この (未訪問) から
グラフ検出アルゴリズム ( BFSが例です) を実行し、発見アルゴリズムの実行中に遭遇したxすべての訪問済みをマークしますx

反復回数 (BFS が呼び出された回数) がグループの数です。

于 2012-08-08T14:09:54.223 に答える