-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathboj_14500ver2
112 lines (92 loc) · 2.75 KB
/
boj_14500ver2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
N , M = map(int,input().split())
tList = []
for _ in range(N):
tList.append(list(map(int,input().split())))
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
visited = [[False for _ in range(M)] for _ in range(N)]
max_sum = -1
def dfs(x, y, num, summ):
global N, M, tList, dx, dy, max_sum
if num == 4:
max_sum = max(max_sum, summ)
return
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= N or ny >= M:
continue
if not visited[nx][ny]:
visited[nx][ny] = True
dfs(nx, ny, num + 1, summ + tList[nx][ny])
visited[nx][ny] = False
def solution():
global N, M, tList, max_sum
for i in range(N):
for j in range(M):
visited[i][j] = True
dfs(i, j, 1, tList[i][j])
visited[i][j] = False
def pink(tList, a, b, max):
for i in range(a-2):
for j in range(b-1):
sum = tList[i][j]+tList[i+1][j]+tList[i+2][j]+tList[i+1][j+1]
if sum > max:
max = sum
sum = 0
for i in range(a-1):
for j in range(b-2):
sum = tList[i+1][j]+tList[i+1][j+1]+tList[i+1][j+2]+tList[i][j+1]
if sum > max:
max = sum
sum = 0
for i in range(a-2):
for j in range(b-1):
sum = tList[i+1][j]+tList[i][j+1]+tList[i+1][j+1]+tList[i+2][j+1]
if sum > max:
max = sum
sum = 0
for i in range(a-1):
for j in range(b-2):
sum = tList[i][j]+tList[i][j+1]+tList[i][j+2]+tList[i+1][j+1]
if sum > max:
max = sum
sum = 0
return max
solution()
max_sum = pink(tList,N,M,max_sum)
print(max_sum)
########################################
best
####################################
import sys; input = sys.stdin.readline
def dfs(r, c, idx, total):
global ans
if idx == 3:
ans = max(ans, total)
return
else:
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
if 0 <= nr < N and 0 <= nc < M and visit[nr][nc] == 0:
if idx == 1:
visit[nr][nc] = 1
dfs(r, c, idx + 1, total + arr[nr][nc])
visit[nr][nc] = 0
visit[nr][nc] = 1
dfs(nr, nc, idx + 1, total + arr[nr][nc])
visit[nr][nc] = 0
N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
visit = [([0] * M) for _ in range(N)]
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
ans = 0
max_val = max(map(max, arr))
for r in range(N):
for c in range(M):
visit[r][c] = 1
dfs(r, c, 0, arr[r][c])
visit[r][c] = 0
print(ans)