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