二次元配列を連番で繋げて埋めるロジック

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
錦織

二次元配列を連番で繋げて埋めるロジック

#1

投稿記事 by 錦織 » 4年前

二次元配列を連番で繋げて埋めたいのですが
ロジックが思い付かずこちらに記載させて頂きました。

1、二次元配列をすべて0で初期化する
2、特定の位置を1とする
3、2で決めた位置から左右上下に連番で数値を割り振る
4、3を繰り返し、すべてのマスを違う数字で埋める

みたいなことをしたいです。

例としましては以下のような形です。
※一筆でイメージ?です。

int array[4][4];

10,9,8,7
11,2,3,6
12,1,4,5
13,14,15,16

現在、近いロジックはできているのですが、
かなり無理やりにソースを書いており改修したいです。

現在のロジックでは、1~3を行い埋まらなくなったらリセットというのをWhile文で回しております。
盤面が小さければ特に問題ないのですが、大きくなればなるほどやばそうでして・・・。

アバター
usao
記事: 1565
登録日時: 6年前

Re: 二次元配列を連番で繋げて埋めるロジック

#2

投稿記事 by usao » 4年前

答えが無いときはどうするのでしょう?
例えば,
int array[3][3];
に対して,
>2、特定の位置を1とする
の段階で,スタート地点をarray[0][1]に指定されたときとか.

錦織

Re: 二次元配列を連番で繋げて埋めるロジック

#3

投稿記事 by 錦織 » 4年前

usao様

ご指摘ありがとうございます!
確かに・・・。定義を変えたら無限ループになってしまいました。

盤面サイズを最低4以上で考えていたので。
こちらありがとうございます。

現状、左右上下に移動できなくなった時の数字を見て
盤面のサイズ分だったら、whileを抜けるようにしております。

4以上ならその場合がなくなる気もするのですがどうなのでしょうか。

たいちう
記事: 418
登録日時: 9年前

Re: 二次元配列を連番で繋げて埋めるロジック

#4

投稿記事 by たいちう » 4年前

真面目に考えると、かなり難しそうな問題なのですが、
盤面の大きさはどの程度までを想定しているのですか?
そして用途は何ですか?場合によってはベターな提案が得られるかも。


> 4以上ならその場合がなくなる気もするのですがどうなのでしょうか。

奇数×奇数なら起こりえるのです。
サイズと出発点が与えられたら、瞬時に判定できるのですが。

錦織

Re: 二次元配列を連番で繋げて埋めるロジック

#5

投稿記事 by 錦織 » 4年前

たいちう様

ありがとうございます。
なるほど・・・Whileで回避できていたのですが可能性があるのですね。
少し違うのですが、下記のようなゲームを作ろうとしております。

http://www.4gamer.net/games/173/G017371/20120704097/

自分の周囲にひとふでで書けるマスが何マスあるか?みたいなのを表示させたいです。

この問題を自動で作るのに連番で割り振り、
定義された範囲内のサイズで1番から分割していきたいと考えております。

chop.chop
記事: 36
登録日時: 4年前

Re: 二次元配列を連番で繋げて埋めるロジック

#6

投稿記事 by chop.chop » 4年前

つまり、この問題は

与えられたグラフにハミルトン路が存在するのかどうか(準ハミルトングラフかどうか)、つまり全ての頂点を一回のみ訪れるパスがあるかという問題に帰結できますね

wikiによると、NP完全らしいので多項式時間での解決は難しそうです……
こちらのサイトが分かりやすいのではないでしょうか
http://www.prefield.com/algorithm/graph ... _path.html

個人的には二次元配列よりは線形双方向リストを上下にもつなげてやったやつの方が作りやすいような気もしますね

たいちう
記事: 418
登録日時: 9年前

Re: 二次元配列を連番で繋げて埋めるロジック

#7

投稿記事 by たいちう » 4年前

リンク先の説明でもどんなゲームか判りませんでした。

> 自分の周囲にひとふでで書けるマスが何マスあるか?みたいなのを表示させたいです。

この部分をもっと厳密に説明することはできますか?
私には伝わらないし、プログラムを作る以上、絶対必要です。

それと最大サイズについてですが、リンク先に表示されている6×6ですか?
この程度ならwhileを使った原始的な方法でも、あまり問題にならないのではないかと。

閉鎖

“C言語何でも質問掲示板” へ戻る