#include <stdlib.h>
#include <stdio.h>
#define S 7
#define M 4
#define N (S*S) / M
int cell(int grid[S][S], int x, int y)
{
if (x < 0 || x >= S) return 0;
if (y < 0 || y >= S) return 0;
return grid[y][x];
}
int solve(int *repo, int grid[S][S], int x, int y)
{
if (y == S) {
int i, j;
for (i = 0; i < 7; i++) {
for (j = 0; j < 7; j++) {
}
}
return 1;
} else {
int nextx = x + 1;
int nexty = y;
int res = 0;
int i;
if (nextx == 7) {
nextx = 0;
nexty++;
}
for (i = 0; i < M + 1; i++) {
if (repo[i] == 0) continue;
if (i && cell(grid, x - 1, y - 1) == i) continue;
if (i && cell(grid, x + 0, y - 1) == i) continue;
if (i && cell(grid, x + 1, y - 1) == i) continue;
if (i && cell(grid, x - 1, y + 0) == i) continue;
grid[y][x] = i;
repo[i]--;
res += solve(repo, grid, nextx, nexty);
grid[y][x] = 0;
repo[i]++;
}
return res;
}
}
int main()
{
int repo[M + 1] = {1, N, N, N, N};
int grid[S][S] = {{0}};
int n;
n = solve(repo, grid, 0, 0);
printf("%d cells, %d groups of %d prisoners: %d\n", S
*S
, M
, N
, n
);
return 0;
}
CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0ZGlvLmg+CgojZGVmaW5lIFMgNwojZGVmaW5lIE0gNAojZGVmaW5lIE4gKFMqUykgLyBNCgppbnQgY2VsbChpbnQgZ3JpZFtTXVtTXSwgaW50IHgsIGludCB5KQp7CiAgICBpZiAoeCA8IDAgfHwgeCA+PSBTKSByZXR1cm4gMDsKICAgIGlmICh5IDwgMCB8fCB5ID49IFMpIHJldHVybiAwOwogICAgCiAgICByZXR1cm4gZ3JpZFt5XVt4XTsKfQoKaW50IHNvbHZlKGludCAqcmVwbywgaW50IGdyaWRbU11bU10sIGludCB4LCBpbnQgeSkKewogICAgaWYgKHkgPT0gUykgeyAgCiAgICAgICAgaW50IGksIGo7CiAgICAgICAgCiAgICAgICAgZm9yIChpID0gMDsgaSA8IDc7IGkrKykgewogICAgICAgICAgICBmb3IgKGogPSAwOyBqIDwgNzsgaisrKSB7CiAgICAgICAgICAgICAgICBwdXRjaGFyKCIuUkdZQiJbZ3JpZFtqXVtpXV0pOwogICAgICAgICAgICB9CiAgICAgICAgICAgIHB1dGNoYXIoMTApOwogICAgICAgIH0KICAgICAgICBwdXRjaGFyKDEwKTsKICAgICAgICAgIAogICAgICAgIHJldHVybiAxOwogICAgfSBlbHNlIHsKICAgICAgICBpbnQgbmV4dHggPSB4ICsgMTsKICAgICAgICBpbnQgbmV4dHkgPSB5OwogICAgICAgIGludCByZXMgPSAwOwogICAgICAgIGludCBpOwogICAgICAgIAogICAgICAgIGlmIChuZXh0eCA9PSA3KSB7CiAgICAgICAgICAgIG5leHR4ID0gMDsKICAgICAgICAgICAgbmV4dHkrKzsKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgZm9yIChpID0gMDsgaSA8IE0gKyAxOyBpKyspIHsKICAgICAgICAgICAgaWYgKHJlcG9baV0gPT0gMCkgY29udGludWU7CiAgICAgICAgICAgIGlmIChpICYmIGNlbGwoZ3JpZCwgeCAtIDEsIHkgLSAxKSA9PSBpKSBjb250aW51ZTsKICAgICAgICAgICAgaWYgKGkgJiYgY2VsbChncmlkLCB4ICsgMCwgeSAtIDEpID09IGkpIGNvbnRpbnVlOwogICAgICAgICAgICBpZiAoaSAmJiBjZWxsKGdyaWQsIHggKyAxLCB5IC0gMSkgPT0gaSkgY29udGludWU7CiAgICAgICAgICAgIGlmIChpICYmIGNlbGwoZ3JpZCwgeCAtIDEsIHkgKyAwKSA9PSBpKSBjb250aW51ZTsKICAgICAgICAgICAgCiAgICAgICAgICAgIGdyaWRbeV1beF0gPSBpOwogICAgICAgICAgICByZXBvW2ldLS07CiAgICAgICAgICAgIAogICAgICAgICAgICByZXMgKz0gc29sdmUocmVwbywgZ3JpZCwgbmV4dHgsIG5leHR5KTsKICAgICAgICAgICAgCiAgICAgICAgICAgIGdyaWRbeV1beF0gPSAwOwogICAgICAgICAgICByZXBvW2ldKys7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIHJldHVybiByZXM7CiAgICB9Cn0KCmludCBtYWluKCkKewogICAgaW50IHJlcG9bTSArIDFdID0gezEsIE4sIE4sIE4sIE59OwogICAgaW50IGdyaWRbU11bU10gPSB7ezB9fTsKICAgIGludCBuOwogICAgCiAgICBuID0gc29sdmUocmVwbywgZ3JpZCwgMCwgMCk7CiAgICAKICAgIHByaW50ZigiJWQgY2VsbHMsICVkIGdyb3VwcyBvZiAlZCBwcmlzb25lcnM6ICVkXG4iLCBTKlMsIE0sIE4sIG4pOwoKICAgIHJldHVybiAwOwp9Cg==