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

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

Решение на 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