# Участник:Easik/largest-plus-sign

Перейти к: навигация, поиск

Решение на Python не прошло по времени, прикладываю его под кодом C++.

C++ \ g++

```class Solution {
public:
int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) {

int cnt = 0;
int res = 0;

vector<vector<int>> dp(N, vector<int>(N, 0));
unordered_set<int> c;

for (auto mine:mines) {

c.insert(N * mine[0] + mine[1]);

}

for (int j = 0; j < N; j++) {

cnt = 0;

// Up
for (int i = 0; i < N; i++) {

cnt = c.count(N * i + j) ? 0 : cnt + 1;
dp[i][j] = cnt;

}

cnt = 0;

// Down
for (int i = N - 1; i >= 0; i--) {

cnt = c.count(N * i + j) ? 0 : cnt + 1;
dp[i][j] = min(dp[i][j], cnt);

}

}

for (int i = 0; i < N; i++) {

cnt = 0;

// Left
for (int j = 0; j < N; j++) {

cnt = c.count(N * i + j) ? 0 : cnt + 1;
dp[i][j] = min(dp[i][j], cnt);

}

cnt = 0;

// Right
for (int j = N - 1; j >= 0; j--) {

cnt = c.count(N * i + j) ? 0 : cnt + 1;
dp[i][j] = min(dp[i][j], cnt);
res = max(dp[i][j], res);

}

}

return res;

}

};```

```from collections import Counter
import numpy as np

class Solution(object):
def orderOfLargestPlusSign(self, N, mines):
"""
:type N: int
:type mines: List[List[int]]
:rtype: int
"""

cnt = 0
res = 0

dp = np.zeros((N, N)).astype(int)
c = Counter()

for mine in mines:
c[N * mine[0] + mine[1]] += 1

for j in range(N):

cnt = 0

# Up
for i in range(N):
if c[N * i + j] != 0:
cnt = 0

else:
cnt = cnt + 1

dp[i][j] = cnt
#print(N * i + j, dp[i][j])
print(c[N * i + j], dp[i][j])

cnt = 0

# Down
for i in range(N - 1, 0 - 1, -1):
if c[N * i + j] != 0:
cnt = 0

else:
cnt = cnt + 1

dp[i][j] = min(dp[i][j], cnt)

for i in range(N):

cnt = 0

# Left
for j in range(N):
if c[N * i + j] != 0:
cnt = 0

else:
cnt = cnt + 1

dp[i][j] = min(dp[i][j], cnt)

cnt = 0

# Right
for j in range(N - 1, 0 - 1, -1):
if c[N * i + j] != 0:
cnt = 0

else:
cnt = cnt + 1

dp[i][j] = min(dp[i][j], cnt)
res = max(dp[i][j], res);

return res```