Существует решение dynamic recursion и аналогичное решение dynamic iteration, которые помогают избежать ошибки переполнения стека из-за глубоких рекурсивных вызовов при очень большом вводе.
Dynami c - рекурсия
Анализ:
* for a 2*2 cell, could simply fill it,
* for a 4*4 cell,
* divide it into 4 2*2 smaller squares,
* first fill the 2*2 square that already has 1 cell filled,
* now the 2*2 square at the center of the original square has 3 empty cells, just fill it with a tile,
* now all the 3 remain 2*2 squares divided in previous step, has 1 cell filled,
* then for each of the 3 remain 2*2 squares, fill with a tile,
*
* for a 8*8 cell,
* divide it into 4 4*4 smaller squares,
* then fill the 4*4 square that already has 1 cell filled, in similar way as a 4*4 input,
* now the 2*2 square at the center of the original square has 3 empty cells, just fill it with a tile,
* now all the 3 remain 4*4 squares divided in previous step, has 1 cell filled,
* then for each of the 3 remain 4*4 squares, fill it in similar way as a 4*4 input,
*
* for a n*n cell,
repeat divide & conquer,
steps:
* if n = 2,
this is base, simple fill a tile,
* else
* divide it into 4 (n/2 * n/2) squares,
* work on the one already with has a tile, by a recursive call,
* then put a tile at center of input cell, to fill the (2*2) square in center,
* then for each of the 3 (n/2 * n/2) squares,
* work on it, by a recursive call,
*
*
*
*
Dynami c - итерация
Аналогично Dynamic - recursion выше, но используется l oop, чтобы избежать глубоких рекурсивных вызовов.
Таким образом, предпочтительнее .
Анализ:
* if it's base case (2*2 square),
it's the same as `Dynamic - recursion`,
* if it's not base case,
* divide it into 4 (n/2 * n/2) squares, mark the one already has a cell filled as A,
* then fill (2*2) square at the center of input square first, leave the cell belong to A empty,
now all the 4 (n/2 * n/2) squares, has a single cell filled,
*
* then loop the 4 (n/2 * n/2) squares, for each:
* work on it, by a recursive call,
*
*
*
Представление форм
Нужны его x и y позиции.
Таким образом структура может выглядеть следующим образом: c:
typedef struct {
int x;
int y;
} Cell;
Может быть 4 направления, пометить как: 1, 2, 3, 4;
И нужна координата средней ячейки L-плитки, чтобы найти ее,
Таким образом, структура может выглядеть так, в c:
typedef struct {
char direction; // 1, 2, 3, 4;
Cell mid; // position of middle cell of tile,
} Tile;
Нужна левая / верхняя ячейка, чтобы решить ее position.
И длина стороны, чтобы определить ее размер.
Таким образом, структура может выглядеть следующим образом: c:
typedef struct {
Cell start; // top/left cell,
int size; // length of side,
} Square;