二次元配列を特定の範囲内のサイズでランダムな形に分割する
二次元配列を特定の範囲内のサイズでランダムな形に分割する
二次元配列を特定の範囲内のサイズでランダムな形に分割したいのですが、よさそうなロジックが思いつきません。
こうしたら簡単にできそう!みたいなアドバイスを頂けないでしょうか。
例)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
みたいな感じです。
わかりにくくてすみません。
問題なのは範囲によって形が変わってしまう事、
全てのマスが埋めたいのですが埋まらないことが出てきてしまう事になります。
こうしたら簡単にできそう!みたいなアドバイスを頂けないでしょうか。
例)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
みたいな感じです。
わかりにくくてすみません。
問題なのは範囲によって形が変わってしまう事、
全てのマスが埋めたいのですが埋まらないことが出てきてしまう事になります。
Re: 二次元配列を特定の範囲内のサイズでランダムな形に分割する
オフトピック
最初は1マスずつばらばらの状態からくっつけていく感じでなんとかなりませんか.
例えば,3*3なら1マスな9個のグループから出発して…
隣接していて合併しても目標最大個数を超えないグループ対 をリストアップして
そのうちの どれか を選んで併合,
というのを繰り返していく感じ,というか.
>埋まらないことが出てきてしまう
これについては併合するグループを選ぶ際に,
・マスの個数が足りない (目標最小個数に達していないやつを優先)
・隣接するマスが少ない (最初は角や辺の場所から優先してくっつけていく.後回しにすると後で困りそうだから)
みたいな条件で優先順位を設けてどうにか回避できないかなぁ
例えば,3*3なら1マスな9個のグループから出発して…
隣接していて合併しても目標最大個数を超えないグループ対 をリストアップして
そのうちの どれか を選んで併合,
というのを繰り返していく感じ,というか.
>埋まらないことが出てきてしまう
これについては併合するグループを選ぶ際に,
・マスの個数が足りない (目標最小個数に達していないやつを優先)
・隣接するマスが少ない (最初は角や辺の場所から優先してくっつけていく.後回しにすると後で困りそうだから)
みたいな条件で優先順位を設けてどうにか回避できないかなぁ
Re: 二次元配列を特定の範囲内のサイズでランダムな形に分割する
1マスの部屋で埋め尽くす;
for (;;) {
if (全ての部屋が範囲内の大きさ) break; // 完成
if (許容範囲より大きい部屋がある) その部屋を1マスの部屋に分割;
許容範囲より小さい部屋をランダムで1つ選ぶ;
ターゲットの部屋の壁が壊せるか壊せないか調べる;
// 壊せない壁とは、外周(A)、または、壊したら許容範囲外の部屋ができてしまう壁(B)
if (壊せる壁がある)
壊せる壁をランダムで1つ選んで壊す;
else
(B)をランダムで1つ選んで壊す;
}
最初の配列が大きく、かつ、許容される範囲が狭い場合、
最終的に解決するとしても時間がかかってしまう恐れがあるので、
その場合は別の工夫が必要になるかもしれません。
> 問題なのは範囲によって形が変わってしまう事、
> 全てのマスが埋めたいのですが埋まらないことが出てきてしまう事になります。
範囲によって形が変わるのは当たり前なので、何が問題なのかわかりません。
私が何か見落としているようなら、ご指摘お願いします。
Re: 二次元配列を特定の範囲内のサイズでランダムな形に分割する
>if (許容範囲より大きい部屋がある) その部屋を1マスの部屋に分割;
なるほど,余ったやつが出たら周辺を巻き込んで局所的にやりなおせばいいということですね.
…ちょっと,やってみました.
効率とかデータの管理方法だとか度外視して”やってみただけ”なのでひどいコードですが.(そのためかやたら長いw)
あまり試してないですが,簡単な問題は解けてる…のかな?
なるほど,余ったやつが出たら周辺を巻き込んで局所的にやりなおせばいいということですね.
…ちょっと,やってみました.
効率とかデータの管理方法だとか度外視して”やってみただけ”なのでひどいコードですが.(そのためかやたら長いw)
あまり試してないですが,簡単な問題は解けてる…のかな?
► スポイラーを表示
Re: 二次元配列を特定の範囲内のサイズでランダムな形に分割する
サイズは、縦も横も 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);
}
Re: 二次元配列を特定の範囲内のサイズでランダムな形に分割する
訂正です。かずま さんが書きました:サイズは、縦も横も 15までです。
15行目 cont --> const
52行目と 60行目は不要(38行目があるから)
67行目の random_shuffle() は 53行目の for文の前に移した方がよい
Re: 二次元配列を特定の範囲内のサイズでランダムな形に分割する
すみません。訂正の訂正です。かずま さんが書きました:67行目の random_shuffle() は 53行目の for文の前に移した方がよい
random_shuffle() をそこに移動させてはいけないことが分かりました。
Re: 二次元配列を特定の範囲内のサイズでランダムな形に分割する
かずまさん。全くわかりません。
お手数ですが簡単な説明をお願いできるでしょうか。
(説明を聞いてもわからなければごめんなさい。
私以外にもわからない人が多くいると思うので、
その場合はご容赦ください。)
私にとって新しい世界が開けるかもしれませんが、
もう少し考えて無理なら諦めます。
お手数ですが簡単な説明をお願いできるでしょうか。
(説明を聞いてもわからなければごめんなさい。
私以外にもわからない人が多くいると思うので、
その場合はご容赦ください。)
私にとって新しい世界が開けるかもしれませんが、
もう少し考えて無理なら諦めます。
Re: 二次元配列を特定の範囲内のサイズでランダムな形に分割する
#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);
}
row = 3, col = 4 なら と初期化されます。
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通り。自分で書き出してみてください。
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キーなしに全パターンをファイルに書き出せま
す。
Re: 二次元配列を特定の範囲内のサイズでランダムな形に分割する
かずまさん。おかげさまで理解できました。
(読めるようになったけど、書ける日が来るだろうか。)
このデータの持ち方は私では思いつきませんね。
再帰で全ての解を得る方法も考えていましたが、
乱数を使うことで全ての解をもつ必要もなくなると。
最後に番兵(?)と{3,15,16}のような形の処理も勉強になりました。
丁寧な説明ありがとうございました。
(読めるようになったけど、書ける日が来るだろうか。)
このデータの持ち方は私では思いつきませんね。
再帰で全ての解を得る方法も考えていましたが、
乱数を使うことで全ての解をもつ必要もなくなると。
最後に番兵(?)と{3,15,16}のような形の処理も勉強になりました。
丁寧な説明ありがとうございました。