Дана матрица размером m x n, где каждая ячейка является либо стеной 'W', либо врагом 'E', либо пустой '0'. return максимальное количество врагов, которых можно уничтожить, используя одну бомбу. Вы можете разместить бомбу только в пустой ячейке.
Бомба уничтожает всех врагов в той же строке и столбце от точки установки до тех пор, пока не встретит стену, так как она слишком сильна, чтобы быть разрушенной.
Example:
Input: grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3
C# solution
matched/originalpublic class Solution {
public int MaxKilledEnemies(char[][] grid) {
if (grid.Length == 0) return 0;
int rows = grid.Length;
int cols = grid[0].Length;
int maxCount = 0;
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col) {
if (grid[row][col] == '0') {
int hits = KillEnemies(row, col, grid);
maxCount = Math.Max(maxCount, hits);
}
}
}
return maxCount;
}
private int KillEnemies(int row, int col, char[][] grid) {
int enemyCount = 0;
int[][] directions = new int[][] {
new int[] {-1, 0}, new int[] {1, 0},
new int[] {0, -1}, new int[] {0, 1}
};
foreach (var dir in directions) {
int r = row + dir[0];
int c = col + dir[1];
while (r >= 0 && r < grid.Length && c >= 0 && c < grid[0].Length) {
if (grid[r][c] == 'W') break;
if (grid[r][c] == 'E') ++enemyCount;
r += dir[0];
c += dir[1];
}
}
return enemyCount;
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int MaxKilledEnemies(char[][] grid) {
if (grid.size() == 0) return 0;
int rows = grid.size();
int cols = grid[0].size();
int maxCount = 0;
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col) {
if (grid[row][col] == '0') {
int hits = KillEnemies(row, col, grid);
maxCount = max(maxCount, hits);
}
}
}
return maxCount;
}
private int KillEnemies(int row, int col, char[][] grid) {
int enemyCount = 0;
int[][] directions = new int[][] {
new int[] {-1, 0}, new int[] {1, 0},
new int[] {0, -1}, new int[] {0, 1}
};
foreach (var dir in directions) {
int r = row + dir[0];
int c = col + dir[1];
while (r >= 0 && r < grid.size() && c >= 0 && c < grid[0].size()) {
if (grid[r][c] == 'W') break;
if (grid[r][c] == 'E') ++enemyCount;
r += dir[0];
c += dir[1];
}
}
return enemyCount;
}
}Java solution
matched/originalclass Solution {
public int maxKilledEnemies(char[][] grid) {
if (grid.length == 0)
return 0;
int rows = grid.length;
int cols = grid[0].length;
int maxCount = 0;
for (int row = 0; row < rows; ++ row) {
for (int col = 0; col < cols; ++ col) {
if (grid[row][col] == '0') {
int hits = this.killEnemies(row, col, grid);
maxCount = Math.max(maxCount, hits);
}
}
}
return maxCount;
}
private int killEnemies(int row, int col, char[][] grid) {
int enemyCount = 0;
for (int c = col - 1; c >= 0; --c) {
if (grid[row][c] == 'W')
break;
else if (grid[row][c] == 'E')
enemyCount += 1;
}
for (int c = col + 1; c < grid[0].length; ++c) {
if (grid[row][c] == 'W')
break;
else if (grid[row][c] == 'E')
enemyCount += 1;
}
for (int r = row - 1; r >= 0; --r) {
if (grid[r][col] == 'W')
break;
else if (grid[r][col] == 'E')
enemyCount += 1;
}
for (int r = row + 1; r < grid.length; ++r) {
if (grid[r][col] == 'W')
break;
else if (grid[r][col] == 'E')
enemyCount += 1;
}
return enemyCount;
}
}Python solution
matched/originalclass Solution:
def maxKilledEnemies(self, grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
max_count = 0
for row in range(rows):
for col in range(cols):
if grid[row][col] == '0':
hits = self.killEnemies(row, col, grid)
max_count = max(max_count, hits)
return max_count
def killEnemies(self, row, col, grid):
enemy_count = 0
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for dr, dc in directions:
r, c = row + dr, col + dc
while 0 <= r < len(grid) and 0 <= c < len(grid[0]):
if grid[r][c] == 'W':
break
elif grid[r][c] == 'E':
enemy_count += 1
r += dr
c += dc
return enemy_countGo solution
matched/originalpackage main
import "fmt"
type Solution struct{}
func (s *Solution) maxKilledEnemies(grid [][]byte) int {
if len(grid) == 0 {
return 0
}
rows := len(grid)
cols := len(grid[0])
maxCount := 0
for row := 0; row < rows; row++ {
for col := 0; col < cols; col++ {
if grid[row][col] == '0' {
hits := s.killEnemies(row, col, grid)
if hits > maxCount {
maxCount = hits
}
}
}
}
return maxCount
}
func (s *Solution) killEnemies(row, col int, grid [][]byte) int {
enemyCount := 0
directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
for _, dir := range directions {
r, c := row+dir[0], col+dir[1]
for r >= 0 && r < len(grid) && c >= 0 && c < len(grid[0]) {
if grid[r][c] == 'W' {
break
}
if grid[r][c] == 'E' {
enemyCount++
}
r += dir[0]
c += dir[1]
}
}
return enemyCount
}
func main() {
grid := [][]byte{
{'0', 'E', '0', '0'},
{'E', '0', 'W', 'E'},
{'0', 'E', '0', '0'},
}
sol := Solution{}
fmt.Println(sol.maxKilledEnemies(grid))
}Algorithm
Перебрать каждую ячейку в сетке и для каждой пустой ячейки вычислить, сколько врагов можно убить, установив бомбу.
Реализовать функцию killEnemies(row, col), которая считает количество врагов, убитых бомбой, установленных в пустой ячейке (row, col), проверяя все четыре направления (влево, вправо, вверх, вниз) до стены или границы сетки.
Вернуть максимальное количество врагов, убитых среди всех пустых ячеек.
😎
Vacancies for this task
Active vacancies with overlapping task tags are shown.
There are no active vacancies yet.