สมมติว่าเรามีเมทริกซ์ 2D ที่มีค่า 3 ค่า คือ 2, 1, และ 0 โดย 2 แทนศัตรู 1 แทนกำแพง และ 0 แทนเซลล์ว่าง เราต้องหาจำนวนศัตรูสูงสุดที่เราสามารถฆ่าได้ด้วยระเบิดหนึ่งลูก ระเบิดจะฆ่าศัตรูทั้งหมดในแถวและคอลัมน์เดียวกันจากจุดวางจนกระทั่งชนกำแพง และเราสามารถวางระเบิดได้เฉพาะที่เซลล์ว่างเท่านั้น
เช่น ถ้าอินพุตเป็น:
ผลลัพธ์จะเป็น 3 เนื่องจากเราสามารถวางระเบิดที่กล่องสีเขียวเพื่อฆ่าศัตรูสูงสุด 3 ตัว
ret := 0
n := จำนวนแถวของ grid, m := จำนวนคอลัมน์ของ grid
กำหนดอาร์เรย์ colCnt ขนาด m
ลูป i จาก 0 ถึง n-1:
ลูป j จาก 0 ถึง m-1:
ถ้า j เป็น 0 หรือ grid[i][j] เป็น 1 ให้:
rowCnt := 0
ถ้า grid[i][j] เป็น 1 ให้ k := j + 1 มิฉะนั้น k := j
ลูป k < m และ grid[i][k] ไม่ใช่ 1: rowCnt += (grid[i][k] == 2)
ถ้า i เป็น 0 หรือ grid[i][j] เป็น 1 ให้:
colCnt[j] := 0
ถ้า grid[i][j] เป็น 1 ให้ k := i + 1 มิฉะนั้น k := i
ลูป k < n และ grid[k][j] ไม่ใช่ 1: colCnt[j] += (grid[k][j] == 2)
ถ้า grid[i][j] เป็น 0 ให้ ret := max(ret, rowCnt + colCnt[j])
คืนค่า ret
ตัวอย่าง
#include <bits/stdc++.h> using namespace std; class Solution { public: int solve(vector<vector<int>>& grid) { int ret = 0; int n = grid.size(); int m = n ? grid[0].size() : 0; int rowCnt = 0; vector<int> colCnt(m); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (!j || grid[i][j] == 1) { rowCnt = 0; int k; if (grid[i][j] == 1) k = j + 1; else k = j; for (; k < m && grid[i][k] != 1; k++) { rowCnt += (grid[i][k] == 2); } } if (!i || grid[i][j] == 1) { colCnt[j] = 0; int k; if (grid[i][j] == 1) k = i + 1; else k = i; for (; k < n && grid[k][j] != 1; k++) { colCnt[j] += (grid[k][j] == 2); } } if (grid[i][j] == 0) { ret = max(ret, rowCnt + colCnt[j]); } } } return ret; } }; main(){ Solution ob; vector<vector<int>> v = { {0,2,0,0}, {2,0,1,2}, {0,2,0,0}}; cout << (ob.solve(v)); }อินพุต
{{0,2,0,0}, {2,0,1,2}, {0,2,0,0}}เอาต์พุต
3
