二次元配列を特定の範囲内のサイズでランダムな形に分割する

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

二次元配列を特定の範囲内のサイズでランダムな形に分割する

#1

投稿記事 by daruma » 10年前

二次元配列を特定の範囲内のサイズでランダムな形に分割したいのですが、よさそうなロジックが思いつきません。
こうしたら簡単にできそう!みたいなアドバイスを頂けないでしょうか。

例)3×3の二次元配列を2~4マスの範囲で分割する

1,2,3
1,2,3
2,2,3

例)4×4の二次元配列を2~4マスの範囲で分割する

1,1,1,2
3,3,1,2
4,3,3,2
4,4,5,5

みたいな感じです。
わかりにくくてすみません。

問題なのは範囲によって形が変わってしまう事、
全てのマスが埋めたいのですが埋まらないことが出てきてしまう事になります。

アバター
usao
記事: 1889
登録日時: 12年前
連絡を取る:

Re: 二次元配列を特定の範囲内のサイズでランダムな形に分割する

#2

投稿記事 by usao » 10年前

オフトピック
最初は1マスずつばらばらの状態からくっつけていく感じでなんとかなりませんか.

例えば,3*3なら1マスな9個のグループから出発して…
隣接していて合併しても目標最大個数を超えないグループ対 をリストアップして
そのうちの どれか を選んで併合,
というのを繰り返していく感じ,というか.


>埋まらないことが出てきてしまう

これについては併合するグループを選ぶ際に,
・マスの個数が足りない (目標最小個数に達していないやつを優先)
・隣接するマスが少ない (最初は角や辺の場所から優先してくっつけていく.後回しにすると後で困りそうだから)
みたいな条件で優先順位を設けてどうにか回避できないかなぁ

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

Re: 二次元配列を特定の範囲内のサイズでランダムな形に分割する

#3

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

コード:

1マスの部屋で埋め尽くす;

for (;;) {
	if (全ての部屋が範囲内の大きさ) break;  // 完成
	if (許容範囲より大きい部屋がある) その部屋を1マスの部屋に分割;

	許容範囲より小さい部屋をランダムで1つ選ぶ;
	
	ターゲットの部屋の壁が壊せるか壊せないか調べる;
	// 壊せない壁とは、外周(A)、または、壊したら許容範囲外の部屋ができてしまう壁(B)

	if (壊せる壁がある)
		壊せる壁をランダムで1つ選んで壊す;
	else
		(B)をランダムで1つ選んで壊す;
}
証明はできないけど千日手のようなことにはならないと思います。
最初の配列が大きく、かつ、許容される範囲が狭い場合、
最終的に解決するとしても時間がかかってしまう恐れがあるので、
その場合は別の工夫が必要になるかもしれません。


> 問題なのは範囲によって形が変わってしまう事、
> 全てのマスが埋めたいのですが埋まらないことが出てきてしまう事になります。

範囲によって形が変わるのは当たり前なので、何が問題なのかわかりません。
私が何か見落としているようなら、ご指摘お願いします。

アバター
usao
記事: 1889
登録日時: 12年前
連絡を取る:

Re: 二次元配列を特定の範囲内のサイズでランダムな形に分割する

#4

投稿記事 by usao » 10年前

>if (許容範囲より大きい部屋がある) その部屋を1マスの部屋に分割;

なるほど,余ったやつが出たら周辺を巻き込んで局所的にやりなおせばいいということですね.

…ちょっと,やってみました.
効率とかデータの管理方法だとか度外視して”やってみただけ”なのでひどいコードですが.(そのためかやたら長いw)

あまり試してないですが,簡単な問題は解けてる…のかな?
► スポイラーを表示

かずま

Re: 二次元配列を特定の範囲内のサイズでランダムな形に分割する

#5

投稿記事 by かずま » 10年前

サイズは、縦も横も 15までです。

コード:

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <ctime>

char t[][4] = {
    {2,1},       {2,16},       {3,1,2},      {3,16,32},
    {3,1,16},    {3,1,17},     {3,16,17},    {3,15,16},
    {4,1,2,3},   {4,16,32,48}, {4,1,16,17},
    {4,1,16,32}, {4,1,17,33},  {4,16,32,33}, {4,16,31,32},
    {4,1,2,16},  {4,1,2,16},   {4,16,17,18}, {4,14,15,16},
    {4,1,2,17},  {4,16,17,32}, {4,15,16,17}, {4,15,16,32},
    {4,1,17,18}, {4,15,16,31}, {4,1,15,16},  {4,16,17,33},
};
cont int N = sizeof(t) / sizeof(t[0]);

int b[16 * 16], row, col;

void print()
{
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++)
            std::cout << std::setw(4) << b[i*16 + j];
        std::endl(std::cout);
    }
}

int ok(int r, int c, int i)
{
    int n = t[i][0];
    for (int j = 1; j < n; j++)
        if (b[r*16 + c + t[i][j]]) return 0;
    return 1;
}

void set(int r, int c, int i, int k)
{
    b[r*16 + c] = k;
    int n = t[i][0];
    for (int j = 1; j < n; j++)
        b[r*16 + c + t[i][j]] = k; 
}

void step(int r, int c, int k)
{
    if (c == col) {
        c = 0;
        if (++r == row) { print(); exit(0); }
    }
    if (b[r*16 + c]) step(r, c+1, k);
    else {
        b[r*16 + c] = k;
        for (int i = 0; i < N; i++) {
            if (ok(r, c, i)) {
                set(r, c, i, k);
                step(r, c+1, k+1);
                set(r, c, i, 0);
            }
        }
        b[r*16 + c] = 0;
    }
}

int main()
{
    std::srand(std::time(0));
    std::random_shuffle(t, t+N);
    std::cout << "input row and col: ";
    std::cin >> row >> col;
    if (!std::cin || row >= 16 || col >= 16) return 1;
    for (int i = 0; i < row; i++) b[i*16 + col] = 999;
    for (int i = 0; i <= col; i++) b[row*16 + i] = 999;
    step(0, 0, 1);
}
実行結果

コード:

input row and col: 5 5
   1   2   3   3   3
   1   2   3   4   5
   6   2   2   4   5
   6   7   7   4   4
   7   7   8   8   8

かずま

Re: 二次元配列を特定の範囲内のサイズでランダムな形に分割する

#6

投稿記事 by かずま » 10年前

かずま さんが書きました:サイズは、縦も横も 15までです。
訂正です。
15行目 cont --> const
52行目と 60行目は不要(38行目があるから)
67行目の random_shuffle() は 53行目の for文の前に移した方がよい

かずま

Re: 二次元配列を特定の範囲内のサイズでランダムな形に分割する

#7

投稿記事 by かずま » 10年前

かずま さんが書きました:67行目の random_shuffle() は 53行目の for文の前に移した方がよい
すみません。訂正の訂正です。
random_shuffle() をそこに移動させてはいけないことが分かりました。

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

Re: 二次元配列を特定の範囲内のサイズでランダムな形に分割する

#8

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

かずまさん。全くわかりません。
お手数ですが簡単な説明をお願いできるでしょうか。
(説明を聞いてもわからなければごめんなさい。
私以外にもわからない人が多くいると思うので、
その場合はご容赦ください。)

私にとって新しい世界が開けるかもしれませんが、
もう少し考えて無理なら諦めます。

かずま

Re: 二次元配列を特定の範囲内のサイズでランダムな形に分割する

#9

投稿記事 by かずま » 10年前

コード:

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <ctime>

char t[][4] = {
     {2,1},       {2,16},       {3,1,2},      {3,16,32},
     {3,1,16},    {3,1,17},     {3,16,17},    {3,15,16},
     {4,1,2,3},   {4,16,32,48}, {4,1,16,17},
     {4,1,16,32}, {4,1,17,33},  {4,16,32,33}, {4,16,31,32},
     {4,1,2,16},  {4,1,2,16},   {4,16,17,18}, {4,14,15,16},
     {4,1,2,17},  {4,16,17,32}, {4,15,16,17}, {4,15,16,32},
     {4,1,17,18}, {4,15,16,31}, {4,1,15,16},  {4,16,17,33},
};
const int N = sizeof(t) / sizeof(t[0]);

int b[16 * 16], row, col;

void print()
{
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++)
            std::cout << std::setw(4) << b[i*16 + j];
        std::endl(std::cout);
    }
    std::cout << "--------------------\n";
    std::cin.get();
}

int ok(int r, int c, int i)
{
    int n = t[i][0];
    for (int j = 1; j < n; j++)
        if (b[r*16 + c + t[i][j]]) return 0;
    return 1;
}

void set(int r, int c, int i, int k)
{
    b[r*16 + c] = k;
    int n = t[i][0];
    for (int j = 1; j < n; j++)
        b[r*16 + c + t[i][j]] = k; 
}

void step(int r, int c, int k)
{
    if (c == col) {
        c = 0;
        if (++r == row) { print(); return; }
    }
    if (b[r*16 + c])
        step(r, c+1, k);
    else
        for (int i = 0; i < N; i++) {
            if (ok(r, c, i)) {
                set(r, c, i, k);
                step(r, c+1, k+1);
                set(r, c, i, 0);
            }
        }
}

int main()
{
    std::srand(std::time(0));
    std::random_shuffle(t, t+N);
    std::cout << "input row and col: ";
    std::cin >> row >> col;
    if (!std::cin || row >= 16 || col >= 16) return 1;
    for (int i = 0; i < row; i++) b[i*16 + col] = 999;
    for (int i = 0; i <= col; i++) b[row*16 + i] = 999;
    step(0, 0, 1);
}
b は 16 x 16 の 2次元配列を 1次元配列に置き換えたものです。
row = 3, col = 4 なら

コード:

    0    0    0    0  999
    0    0    0    0  999
    0    0    0    0  999
  999  999  999  999  999
と初期化されます。

r行 c列のマスは、b[r*16 + c] で参照できます。
その右隣は +1、下は +16 です。

この領域 b を 2~4マスの部分領域で埋めたいわけです。

コード:

2マスは、次の 2通り。
+--+--+  +--+
| 0| 1|  | 0|
+--+--+  +--+
         |16|
         +--+

3マスは、次の 6通り。
+--+--+--+  +--+  +--+--+  +--+--+  +--+        +--+
| 0| 1| 2|  | 0|  | 0| 1|  | 0| 1|  | 0|        | 0|
+--+--+--+  +--+  +--+--+  +--+--+  +--+--+  +--+--+
            |16|  |16|        |17|  |16|17|  |15|16|
            +--+  +--+        +--+  +--+--+  +--+--+
            |32|
            +--+

4マスは、19通り。自分で書き出してみてください。
これが t[N][4] で、N = 27 のパターンがあります。
0 は不要なので、ここにマスのサイズを入れています。

あとは、b[0] から順番に、
b[r*16+c] が 0 でなければ、すでに埋まっているので次の b[r*16+c+1] に行く。
b[r*16+c] が 0 なら、そこに 27通りのパターンのうちの一つ t が置けるか
どうか ok()で 見て、置ければ set(r, c, i, k) で置き、右隣に (k+1)番目の
部分領域を置きに行きます。戻ってきたら、set(r, c, i, 0) で tを外します。

r = row, c = col になったら、全部埋まったので print() で表示します。
ここで exit() で終了する代わりに、return で戻ると全パターンを表示します。
cin.get() で止まるので、Enterキーを押して、次の解を表示します。

$ echo 3 3 | ./a.out >file で、Enterキーなしに全パターンをファイルに書き出せま
す。

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

Re: 二次元配列を特定の範囲内のサイズでランダムな形に分割する

#10

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

かずまさん。おかげさまで理解できました。
(読めるようになったけど、書ける日が来るだろうか。)

このデータの持ち方は私では思いつきませんね。
再帰で全ての解を得る方法も考えていましたが、
乱数を使うことで全ての解をもつ必要もなくなると。
最後に番兵(?)と{3,15,16}のような形の処理も勉強になりました。

丁寧な説明ありがとうございました。

かずま

Re: 二次元配列を特定の範囲内のサイズでランダムな形に分割する

#11

投稿記事 by かずま » 10年前

バグがありました。

コード:

    for (int i = 0; i < row; i++) b[i*16 + col] = 999;

コード:

	for (int i = 0; i < row; i++) b[i*16 + col] = b[i*16 + 15] = 999;
に修正します。

かずま

Re: 二次元配列を特定の範囲内のサイズでランダムな形に分割する

#12

投稿記事 by かずま » 10年前

さらにバグは続きます。

コード:

	 {4,1,2,16},  {4,1,2,16},   {4,16,17,18}, {4,14,15,16},
同じ形がありますね。これを次のように修正します。

コード:

	 {4,1,2,16},  {4,1,2,18},   {4,16,17,18}, {4,14,15,16},

閉鎖

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