Участник:Easik/largest-plus-sign — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 74: Строка 74:
 
      
 
      
 
};
 
};
<\code-cpp>
+
</code-cpp>

Версия 19:56, 14 декабря 2020

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;
 
    }
 
};