Re: [閒聊] 每日leetcode
大風起兮 雲飛揚
安得猛士兮 走四方
原本想說八皇后
看一下 m, n <= 10e5
讓阿瓜走四方好像不太好
一隻阿瓜m+n
放滿mn（m+n) 不太對
直接陣列四個方向掃過去惹
class Solution {
public:
int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {
//empty: 0, gaurd: 1, wall: 2, see: -1
vector<vector<int>> mat(m, vector<int>(n, 0));
for(auto& g: guards){
mat[g[0]][g[1]] = 1;
}
for(auto& w: walls){
mat[w[0]][w[1]] = 2;
}
//m row, n col
//see right
for(int i = 0; i < m; i++){
int see = 0;
for(int j = 0; j < n; j++){
if(mat[i][j] == 0) mat[i][j] = see;
else if(mat[i][j] == 1) see = -1;
else if(mat[i][j] == 2) see = 0;
}
}
//see left
for(int i = 0; i < m; i++){
int see = 0;
for(int j = n-1; j >= 0; j--){
if(mat[i][j] == 0) mat[i][j] = see;
else if(mat[i][j] == 1) see = -1;
else if(mat[i][j] == 2) see = 0;
}
}
//see down
for(int j = 0; j < n; j++){
int see = 0;
for(int i = 0; i < m; i++){
if(mat[i][j] == 0) mat[i][j] = see;
else if(mat[i][j] == 1) see = -1;
else if(mat[i][j] == 2) see = 0;
}
}
//see up
for(int j = 0; j < n; j++){
int see = 0;
for(int i = m-1; i >= 0; i--){
if(mat[i][j] == 0) mat[i][j] = see;
else if(mat[i][j] == 1) see = -1;
else if(mat[i][j] == 2) see = 0;
}
}
//count
int cnt = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(mat[i][j] == 0) cnt++;
}
}
return cnt;
}
};
後來發現early return的話
其實把阿瓜放滿
走四方worse case也是4mn
m*n 也<= 10e5
想不到什麼厲害解法
如果不能m*n的話甚至不能整個掃一遍
m*n再去扣掉或是bitwise
好像很強==
※ 引述《JIWP (神楽めあ的錢包)》之銘言：
: 2257. Count Unguarded Cells in the Grid
: 有m*n的二維矩陣
: 在這個二維矩陣上有守衛和牆壁
: 守衛可以看向4個方向(東西南北)直到被牆壁擋住
: 請問這個矩陣上有個cell是不會被守衛看到的?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1732204631.A.D72.html