結果
| 問題 | No.2958 Placing Many L-s |
| ユーザー |
👑  ygussany
|
| 提出日時 | 2024-11-08 23:30:33 |
| 言語 | C (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 30 ms / 2,000 ms |
| コード長 | 6,198 bytes |
| コンパイル時間 | 378 ms |
| コンパイル使用メモリ | 35,392 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-11-08 23:30:37 |
| 合計ジャッジ時間 | 3,445 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 29 |
ソースコード
#include <stdio.h>
int naive(int N, int M, int ans[][501], int k)
{
int i, j;
for (i = 1; i <= N; i++) {
for (j = 1; j <= M; j++) if (ans[i][j] == 0) break;
if (j <= M) break;
}
if (i > N) return 1;
if (i <= N - 2 && j <= M - 1) {
if (ans[i][j] == 0 && ans[i][j+1] == 0 && ans[i+1][j] == 0 && ans[i+2][j] == 0) {
ans[i][j] = k;
ans[i][j+1] = k;
ans[i+1][j] = k;
ans[i+2][j] = k;
if (naive(N, M, ans, k + 1) != 0) return 1;
ans[i][j] = 0;
ans[i][j+1] = 0;
ans[i+1][j] = 0;
ans[i+2][j] = 0;
}
if (ans[i][j] == 0 && ans[i][j+1] == 0 && ans[i+1][j+1] == 0 && ans[i+2][j+1] == 0) {
ans[i][j] = k;
ans[i][j+1] = k;
ans[i+1][j+1] = k;
ans[i+2][j+1] = k;
if (naive(N, M, ans, k + 1) != 0) return 1;
ans[i][j] = 0;
ans[i][j+1] = 0;
ans[i+1][j+1] = 0;
ans[i+2][j+1] = 0;
}
if (ans[i][j] == 0 && ans[i+1][j] == 0 && ans[i+2][j] == 0 && ans[i+2][j+1] == 0) {
ans[i][j] = k;
ans[i+1][j] = k;
ans[i+2][j] = k;
ans[i+2][j+1] = k;
if (naive(N, M, ans, k + 1) != 0) return 1;
ans[i][j] = 0;
ans[i+1][j] = 0;
ans[i+2][j] = 0;
ans[i+2][j+1] = 0;
}
}
if (i <= N - 2 && j >= 2) {
if (ans[i][j] == 0 && ans[i+1][j] == 0 && ans[i+2][j] == 0 && ans[i+2][j-1] == 0) {
ans[i][j] = k;
ans[i+1][j] = k;
ans[i+2][j] = k;
ans[i+2][j-1] = k;
if (naive(N, M, ans, k + 1) != 0) return 1;
ans[i][j] = 0;
ans[i+1][j] = 0;
ans[i+2][j] = 0;
ans[i+2][j-1] = 0;
}
}
if (i <= N - 1 && j <= M - 2) {
if (ans[i][j] == 0 && ans[i][j+1] == 0 && ans[i][j+2] == 0 && ans[i+1][j] == 0) {
ans[i][j] = k;
ans[i][j+1] = k;
ans[i][j+2] = k;
ans[i+1][j] = k;
if (naive(N, M, ans, k + 1) != 0) return 1;
ans[i][j] = 0;
ans[i][j+1] = 0;
ans[i][j+2] = 0;
ans[i+1][j] = 0;
}
if (ans[i][j] == 0 && ans[i][j+1] == 0 && ans[i][j+2] == 0 && ans[i+1][j+2] == 0) {
ans[i][j] = k;
ans[i][j+1] = k;
ans[i][j+2] = k;
ans[i+1][j+2] = k;
if (naive(N, M, ans, k + 1) != 0) return 1;
ans[i][j] = 0;
ans[i][j+1] = 0;
ans[i][j+2] = 0;
ans[i+1][j+2] = 0;
}
if (ans[i][j] == 0 && ans[i+1][j] == 0 && ans[i+1][j+1] == 0 && ans[i+1][j+2] == 0) {
ans[i][j] = k;
ans[i+1][j] = k;
ans[i+1][j+1] = k;
ans[i+1][j+2] = k;
if (naive(N, M, ans, k + 1) != 0) return 1;
ans[i][j] = 0;
ans[i+1][j] = 0;
ans[i+1][j+1] = 0;
ans[i+1][j+2] = 0;
}
}
if (i <= N - 1 && j >= 3) {
if (ans[i][j] == 0 && ans[i+1][j] == 0 && ans[i+1][j-1] == 0 && ans[i+1][j-2] == 0) {
ans[i][j] = k;
ans[i+1][j] = k;
ans[i+1][j-1] = k;
ans[i+1][j-2] = k;
if (naive(N, M, ans, k + 1) != 0) return 1;
ans[i][j] = 0;
ans[i+1][j] = 0;
ans[i+1][j-1] = 0;
ans[i+1][j-2] = 0;
}
}
return 0;
}
int solve(int N, int M, int ans[][501])
{
if (N * M % 4 != 0 || N == 1 || M == 1 || (N % 4 == 2 && M % 4 == 2) || (N % 8 == 4 && M % 2 == 1) || (N % 2 == 1 && M % 8 == 4)) return 0;
int i, j, k = 1;
if (N % 4 == 0 && M % 2 == 0) {
for (i = 1; i <= N; i += 4) {
for (j = 1; j <= M; j += 2) {
ans[i][j] = k;
ans[i][j+1] = k;
ans[i+1][j] = k;
ans[i+1][j+1] = k + 1;
ans[i+2][j] = k;
ans[i+2][j+1] = k + 1;
ans[i+3][j] = k + 1;
ans[i+3][j+1] = k + 1;
k += 2;
}
}
} else if (N % 2 == 0 && M % 4 == 0) {
for (i = 1; i <= N; i += 2) {
for (j = 1; j <= M; j += 4) {
ans[i][j] = k;
ans[i][j+1] = k;
ans[i][j+2] = k;
ans[i][j+3] = k + 1;
ans[i+1][j] = k;
ans[i+1][j+1] = k + 1;
ans[i+1][j+2] = k + 1;
ans[i+1][j+3] = k + 1;
k += 2;
}
}
} else if (N % 8 == 0) {
for (i = 1; i <= N; i += 8) {
ans[i][1] = k;
ans[i][2] = k;
ans[i][3] = k;
ans[i+1][1] = k;
ans[i+1][2] = k + 1;
ans[i+1][3] = k + 1;
ans[i+2][1] = k + 2;
ans[i+2][2] = k + 2;
ans[i+2][3] = k + 1;
ans[i+3][1] = k + 2;
ans[i+3][2] = k + 3;
ans[i+3][3] = k + 1;
ans[i+4][1] = k + 2;
ans[i+4][2] = k + 3;
ans[i+4][3] = k + 4;
ans[i+5][1] = k + 3;
ans[i+5][2] = k + 3;
ans[i+5][3] = k + 4;
ans[i+6][1] = k + 5;
ans[i+6][2] = k + 4;
ans[i+6][3] = k + 4;
ans[i+7][1] = k + 5;
ans[i+7][2] = k + 5;
ans[i+7][3] = k + 5;
k += 6;
for (j = 4; j <= M; j += 2) {
ans[i][j] = k;
ans[i][j+1] = k;
ans[i+1][j] = k;
ans[i+1][j+1] = k + 1;
ans[i+2][j] = k;
ans[i+2][j+1] = k + 1;
ans[i+3][j] = k + 1;
ans[i+3][j+1] = k + 1;
ans[i+4][j] = k + 2;
ans[i+4][j+1] = k + 2;
ans[i+5][j] = k + 2;
ans[i+5][j+1] = k + 3;
ans[i+6][j] = k + 2;
ans[i+6][j+1] = k + 3;
ans[i+7][j] = k + 3;
ans[i+7][j+1] = k + 3;
k += 4;
}
}
} else {
static int _ans[501][501];
for (i = 1; i <= M; i += 8) {
_ans[i][1] = k;
_ans[i][2] = k;
_ans[i][3] = k;
_ans[i+1][1] = k;
_ans[i+1][2] = k + 1;
_ans[i+1][3] = k + 1;
_ans[i+2][1] = k + 2;
_ans[i+2][2] = k + 2;
_ans[i+2][3] = k + 1;
_ans[i+3][1] = k + 2;
_ans[i+3][2] = k + 3;
_ans[i+3][3] = k + 1;
_ans[i+4][1] = k + 2;
_ans[i+4][2] = k + 3;
_ans[i+4][3] = k + 4;
_ans[i+5][1] = k + 3;
_ans[i+5][2] = k + 3;
_ans[i+5][3] = k + 4;
_ans[i+6][1] = k + 5;
_ans[i+6][2] = k + 4;
_ans[i+6][3] = k + 4;
_ans[i+7][1] = k + 5;
_ans[i+7][2] = k + 5;
_ans[i+7][3] = k + 5;
k += 6;
for (j = 4; j <= N; j += 2) {
_ans[i][j] = k;
_ans[i][j+1] = k;
_ans[i+1][j] = k;
_ans[i+1][j+1] = k + 1;
_ans[i+2][j] = k;
_ans[i+2][j+1] = k + 1;
_ans[i+3][j] = k + 1;
_ans[i+3][j+1] = k + 1;
_ans[i+4][j] = k + 2;
_ans[i+4][j+1] = k + 2;
_ans[i+5][j] = k + 2;
_ans[i+5][j+1] = k + 3;
_ans[i+6][j] = k + 2;
_ans[i+6][j+1] = k + 3;
_ans[i+7][j] = k + 3;
_ans[i+7][j+1] = k + 3;
k += 4;
}
}
for (i = 1; i <= N; i++) for (j = 1; j <= M; j++) ans[i][j] = _ans[j][i];
}
return 1;
}
int main()
{
int T, N, M, ans[501][501] = {}, i, j;
scanf("%d", &T);
while (T--) {
scanf("%d %d", &N, &M);
if (solve(N, M, ans) == 0) printf("-1\n");
else {
printf("%d\n", N * M / 4);
for (i = 1; i <= N; i++) {
for (j = 1; j <= M; j++) printf("%d ", ans[i][j]);
printf("\n");
}
}
}
fflush(stdout);
return 0;
}