大風起兮 雲飛揚 安得猛士兮 走四方 原本想說八皇后 看一下 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