https://codeforces.com/contest/1520/problem/C
시간 4초, 메모리 256MB
input :
- t (1 ≤ t ≤ 100)
- n (1 ≤ n ≤ 100)
output :
- For each test case, output:
-1, if the required matrix does not exist;
the required matrix, otherwise (any such matrix if many of them exist).
행렬이 존재하지 않은 경우에는 -1을 그렇지 않은 경우에는 그 행렬을 출력하시오.
조건 :
-
We will consider the numbers a and b as adjacent if they differ by exactly one, that is, |a−b|=1.
인접한 a와 b의 차의 절대값이 1이 아니게 구성하려 한다. -
We will consider cells of a square matrix n×n as adjacent if they have a common side, that is, for cell (r,c) cells (r,c−1), (r,c+1), (r−1,c) and (r+1,c) are adjacent to it.
n * n 짜리 행렬을 구성하려 한다. r, c를 기준으로 위, 아래, 오른쪽, 왼쪽을 인접하다고 한다.
1 차이 나는 놈들을 띄워 놔야 한다.
처음에 하려 한거는 홀수, 짝수로 나눠ㅓㅅ 하려 했는데 이게 안되네....?
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
어떻게 하면 될까.
체스
체스판을 구성하듯 나열해보자 격자 무늬 색칠 하듯이 각 위치에 순서대로 수를 나열 한다면
1차이 나는 놈들은 다 띄워놓게 되고 먼저 채운 뒤에
나머지를 채우는 경우에는 이미 수 차이가 크기 때문에 생각을 안 해줘도 된다.
구현
현재 행이 홀수인지 짝수인지에 따라 시작하는 인덱스의 값이 달라진다.
그리고 얘네들은 다들 2칸 차이로 움직이기 때문에 증감식이 달라야 한다.
예외
n이 2인 경우에는 어떻게 하든간에 만들수가 없다.
그래서 그 때는 그냥 -1을 출력한다.
import sys
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
t = int(sys.stdin.readline())
for _ in range(t):
n = int(sys.stdin.readline())
ans = [[0] * n for j in range(n)]
if n == 2:
print(-1)
continue
cur = 1
for i in range(n):
for j in range(i % 2, n, 2):
ans[i][j] = cur
cur += 1
for i in range(n):
for j in range((i + 1) % 2, n, 2):
ans[i][j] = cur
cur += 1
for i in range(n):
for j in range(n):
print(ans[i][j], end=' ')
print()
