막히는 문제 풀다가 푸는 요령을 좀 안것 같아서 씀.
문제의 핵심을 알아내는 것이 중요하다.. 어찌보면 당연하지만
스스로 테스트케이스 여러가지 만들어내면서 정답이 되는 조건을 생각해서 풀어냄. 작은 경우부터 만족시키면서 점점 더 크게..
# 387 ms
import sys
sys.stdin = open("input2.txt", "r")
def is_safe(now_r,now_c):
now_e = H[now_r][now_c]
y_bool = True
x_bool = True
# 아래 위
for i in [1,3]:
new_y = now_r + dy[i]
new_x = now_c + dx[i]
while 0 <= new_y < N and 0 <= new_x < M:
if H[new_y][new_x] > now_e:
y_bool = False
break
new_y += dy[i]
new_x += dx[i]
if not(y_bool): break
# 왼쪽 오른쪽
for i in [0,2]:
new_y = now_r + dy[i]
new_x = now_c + dx[i]
while 0 <= new_y < N and 0 <= new_x < M:
if H[new_y][new_x] > now_e:
x_bool = False
new_y += dy[i]
new_x += dx[i]
if not(x_bool): break
return y_bool or x_bool
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
# ///////////////////////////////////////////////////////////////////////////////////
N, M = map(int, input().split())
H = [[0] * M for _ in range(N)]
for i in range(N):
H[i] = list(map(int, input().split()))
# print(*H,sep='\n')
# 왼쪽, 아래, 오른쪽, 위
dy = [0, 1, 0, -1]
dx = [-1, 0, 1, 0]
result = True
for r in range(N):
for c in range(M):
if not(is_safe(r,c)):
result = False
if not(result): break
result_string = "YES"
if not(result): result_string = "NO"
print("#{}".format(test_case), result_string)
# ///////////////////////////////////////////////////////////////////////////////////
밑에는 핵심 파악 뒤 개선 버전
# 258 ms
import sys
sys.stdin = open("input2.txt", "r")
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
# ///////////////////////////////////////////////////////////////////////////////////
N, M = map(int, input().split())
Row_max = [0] * N
H = [[0] * M for _ in range(N)]
for i in range(N):
H[i] = list(map(int, input().split()))
Row_max[i] = max(H[i])
# print(*H,sep='\n')
Col_max = [0] * M
HR = [0 for _ in range(M)]
for i, c in enumerate(zip(*H)):
HR[i] = list(c)
Col_max[i] = max(HR[i])
# 왼쪽, 아래, 오른쪽, 위
dy = [0, 1, 0, -1]
dx = [-1, 0, 1, 0]
# print(Row_max,Col_max)
result = True
for r in range(N):
for c in range(M):
if H[r][c] < Row_max[r] and H[r][c] < Col_max[c]:
result = False
break
if not(result): break
result_string = "YES"
if not(result): result_string = "NO"
print("#{}".format(test_case), result_string)
# ///////////////////////////////////////////////////////////////////////////////////
