Разрежь прямоугольник на равные части!

Представим, что дан прямоугольник, состоящий из w × h квадратов-клеточек, как в школьной тетради по арифметике.

Если w и h вместе не являются нечётными числами, то можно вырезать путь в прямоугольнике по краям клеточек так, чтобы прямоугольник разделился на две соединённые части одинаковой формы (с точностью до поворота одной из частей на 180 градусов, в общем, как в задаче о разрезании шахматной доски на 4 части, только на две :).

Вот решения для w = 4 и h = 3, единица и двойка означают клеточки, относящиеся к первой и второй частям соответственно.

2222   2111   2222
1122   2211   2121
1111   2221   1111

2221   2222   2221
2121   2211   2211
2111   1111   2111

2222   2111   2211
1212   2121   2211
1111   2221   2211

Ниже прилагается программка на консольном C++ для решения данной проблемы.

Код проверен в консоли Visual Studio 2015 (пустой проект, потом добавить файл исходного кода).

Имейте в виду, что для размерности 10 x 10 решений будет уже 1 124 140 214.

#include <iostream>
#include <cstdlib>
using namespace std;

int w, h,      //ширина и высота прямоугольника, 
    show_full; //показывать ли решения целиком
unsigned long cnt = 0; //общее количество решений
unsigned char **hor, **ver, **vis;

unsigned char ** alloc2 (int w, int h) {
 int i;
 unsigned char **x = (unsigned char **)calloc (1, sizeof(unsigned char*) * h + h * w);
 x[0] = (unsigned char *) &x[h];
 for (i = 1; i < h; i++) x[i] = x[i - 1] + w;
 return x;
}

void show() {
 int i, j, v, last_v;
 cout << cnt << ")" << endl;
 for (i = 0; i < h; i++) {
  if (!i) v = last_v = 0;
  else last_v = v = hor[i][0] ? !last_v : last_v;
  for (j = 0; j < w; v = ver[i][++j] ? !v : v) cout << (v ? "1" : "2");
  cout << endl;
 }
 cout << endl;
}

void walk (int y, int x) {
 if (x < 0 || y < 0 || x > w || y > h) return;
 if (!x || !y || x == w || y == h) {
  ++cnt;
  if (show_full) show();
  return;
 }
 if (vis[y][x]) return;
 vis[y][x]++; vis[h - y][w - x]++;
 if (x && !hor[y][x - 1]) {
  hor[y][x - 1] = hor[h - y][w - x] = 1;
  walk(y, x - 1);
  hor[y][x - 1] = hor[h - y][w - x] = 0;
 }
 if (x < w && !hor[y][x]) {
  hor[y][x] = hor[h - y][w - x - 1] = 1;
  walk(y, x + 1);
  hor[y][x] = hor[h - y][w - x - 1] = 0;
 }
 if (y && !ver[y - 1][x]) {
  ver[y - 1][x] = ver[h - y][w - x] = 1;
  walk(y - 1, x);
  ver[y - 1][x] = ver[h - y][w - x] = 0;
 }
 if (y < h && !ver[y][x]) {
  ver[y][x] = ver[h - y - 1][w - x] = 1;
  walk(y + 1, x);
  ver[y][x] = ver[h - y - 1][w - x] = 0;
 }
 vis[y][x]--; vis[h - y][w - x]--;
}

void cut(void) {
 if (1 & (h * w)) return;
 hor = alloc2(w + 1, h + 1);
 ver = alloc2(w + 1, h + 1);
 vis = alloc2(w + 1, h + 1);
 if (h & 1) {
  ver[h / 2][w / 2] = 1;
  walk(h / 2, w / 2);
 }
 else if (w & 1) {
  hor[h / 2][w / 2] = 1;
  walk(h / 2, w / 2);
 }
 else {
  vis[h / 2][w / 2] = 1;
  hor[h / 2][w / 2 - 1] = hor[h / 2][w / 2] = 1;
  walk(h / 2, w / 2 - 1);
  hor[h / 2][w / 2 - 1] = hor[h / 2][w / 2] = 0;
  ver[h / 2 - 1][w / 2] = ver[h / 2][w / 2] = 1;
  walk(h / 2 - 1, w / 2);
 }
}

void cwalk(int y, int x, int d) {
 if (!y || y == h || !x || x == w) {
  ++cnt;
  return;
 }
 vis[y][x] = vis[h - y][w - x] = 1;
 if (x && !vis[y][x - 1]) cwalk(y, x - 1, d | 1);
 if ((d & 1) && x < w && !vis[y][x + 1]) cwalk(y, x + 1, d | 1);
 if (y && !vis[y - 1][x]) cwalk(y - 1, x, d | 2);
 if ((d & 2) && y < h && !vis[y + 1][x]) cwalk(y + 1, x, d | 2);
 vis[y][x] = vis[h - y][w - x] = 0;
}

void count_only () {
 int t;
 long res;
 if (h * w & 1) return;
 if (h & 1) t = h, h = w, w = t;
 vis = alloc2 (w + 1, h + 1);
 vis[h / 2][w / 2] = 1;
 if (w & 1) vis[h / 2][w / 2 + 1] = 1;
 if (w > 1) {
  cwalk(h / 2, w / 2 - 1, 1);
  res = 2 * cnt - 1;
  cnt = 0;
  if (w != h) cwalk(h / 2 + 1, w / 2, (w & 1) ? 3 : 2);
  res += 2 * cnt - !(w & 1);
 }
 else res = 1;
 if (w == h) res = 2 * res + 2;
 cnt = res;
}

int main () {
 w = 4;
 h = 3;
 show_full = 1;
 
 if (show_full) cut(); //Показать решения
 else count_only(); //Только количество

 cout << "Count=" << cnt << endl;
 cin.get();
 return 0;
}

16.10.2019, 15:31 [1259 просмотров]