leetcode 764. Largest Plus Sign 最大加号标志

Problem: 764. Largest Plus Sign 最大加号标志

解题过程

对每个格子，计算左右上下的1的个数的最小值。队列会超时，也就是广度优先搜索会超时

首先排序，然后按行放入=0的列索引，按列放入=0的行索引，最后循环，计算left、right、up、down几个方向的1的个数，拿最小值，然后结果取最大值。左侧1的个数按行从后面开始访问若列索引<j则break，右侧1的个数按行从前面开始访问若列索引>j则break，初始化int left=j+1, right=n-j, up=i+1, down=n-i;

若是直接数matrix的1个数，会超时，只能按行放入列索引，按列放入行索引

Code

class Solution { public: // int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; bool status[250001]; int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) { // queue<vector<int>> qe; // unordered_set<int> te; // memset(status, 0, sizeof(status)); // for(int i = 0; i < mines.size(); i++) { // te.insert((mines[i][0] << 20) + mines[i][1]); // } sort(mines.begin(), mines.end(), [=](vector<int>&a, vector<int>&c) { if(a[0]==c[0]) return a[1] < c[1]; else return a[0] < c[0]; }); // vector<vector<bool>> matrix(n, vector<bool>(n, true)); vector<vector<int>> row(501); vector<vector<int>> column(501); for(int i = 0; i < mines.size(); i++) { // matrix[mines[i][0]][mines[i][1]] = false; // te.insert(mines[i][0] * n + mines[i][1]); row[mines[i][0]].push_back(mines[i][1]); column[mines[i][1]].push_back(mines[i][0]); status[mines[i][0] * n + mines[i][1]] = true; } int mx = 0, key; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { // key = i * n + j; // if(matrix[i][j]) { // if(te.find(i * n + j) == te.end()) { if(status[i*n+j]==false) { int left=j+1, right=n-j, up=i+1, down=n-i; for(int k = row[i].size()-1; k >= 0; k--) { // key = i * n + k; if(row[i][k] < j) { left = j - row[i][k]; break; } // if(matrix[i][k]==false) break; // left++; } for(int k = 0; k < row[i].size(); k++) { // key = i * n + k; // if(matrix[i][k]==false) break; // right++; if(row[i][k] > j) { right = row[i][k] - j; break; } } for(int k = column[j].size()-1; k >= 0; k--) { // key = k * n + j; // if(matrix[k][j]==false) break; // up++; if(column[j][k] < i) { up = i - column[j][k]; break; } } for(int k = 0; k < column[j].size(); k++) { // key = k * n + j; // if(matrix[k][j]==false) break; // down++; if(column[j][k] > i) { down = column[j][k] - i; break; } } mx = max(mx, min(left, min(right, min(up, down)))); } } } return mx; // for(int i = 0; i < n; i++) { // for(int j = 0; j < n; j++) { // key = (i << 20) + j; // if(te.find(key)==te.end()) { // num++; // qe.push( { i, j, num, -1, 0} ); // qe.push( { i, j, num, 1, 0} ); // qe.push( { i, j, num, 0, -1} ); // qe.push( { i, j, num, 0, 1} ); // } // } // } // if(qe.size() == 0) return 0; // int x, y, cnt = 1; // unordered_set<int> tee; // while(!qe.empty()) { // int sz = qe.size(); // bool add = false; // unordered_map<int, int> ump; // for(int i = 0; i < sz; i++) { // vector<int> pir = qe.front(); // qe.pop(); // if(status[pir[2]]) { // continue; // } // x = pir[0] + pir[3]; // y = pir[1] + pir[4]; // key = (x << 20) + y; // if(x < 0 || y < 0 || x >= n || y >= n || te.find(key)!=te.end()) { // status[pir[2]] = true; // continue; // } // qe.push({x, y, pir[2], pir[3], pir[4]}); // ump[pir[2]]++; // } // bool find = false; // for(auto& [key, val] : ump) { // if(val==4) { // find = true; // break; // } // } // if(find == false) { // return cnt; // } else { // cnt++; // } // } // return cnt; } };