План курса / Все задачи / Алгоритмы и структуры данных

Под боем королевы

средне

Дан двухмерный массив целых чисел board. Нужно найти максимальную сумму клеток, которые бьет шахматная королева, если поставить ее на доску, включая клетку с самой королевой.

Пример 1:

Ввод: board =
[[3,2,5,1]
,[4,9,1,3]
,[2,9,2,1]]
Вывод: 40
Объяснение: получим сумму 40 если поставить королеву на клетку [1,1] (индексация с 0).

Пример 2:

Ввод: board = [[1,2,3]]
Вывод: 6

Ограничения:

len(board) >= 1
len(board[i]) >= 1

public class Solution
{
    public static int MaxQueenSum(List<List<int>> board)
    {
        List<int> rowsSum = new List<int>(new int[board.Count]);
        List<int> colsSum = new List<int>(new int[board[0].Count]);
        List<int> d1Sum = new List<int>(new int[board.Count + board[0].Count - 1]);
        List<int> d2Sum = new List<int>(new int[board.Count + board[0].Count - 1]);

        // Предподсчет сумм строк, столбцов и диагоналей
        for (int i = 0; i < board.Count; ++i)
        {
            for (int j = 0; j < board[i].Count; ++j)
            {
                int val = board[i][j];
                rowsSum[i] += val;
                colsSum[j] += val;
                d1Sum[(board.Count - 1 - i) + j] += val;
                d2Sum[i + j] += val;
            }
        }

        int maxSum = 0;
        for (int i = 0; i < board.Count; ++i)
        {
            for (int j = 0; j < board[i].Count; ++j)
            {
                // Сумма строки, столбца и двух диагоналей
                // Минус 3x серединный элемент (он посчитан 4 раза)
                int currSum = rowsSum[i] + colsSum[j];
                currSum += d1Sum[(board.Count - 1 - i) + j] + d2Sum[i + j];
                currSum -= 3 * board[i][j];

                if (i == 0 && j == 0)
                {
                    maxSum = currSum;
                }
                maxSum = Math.Max(maxSum, currSum);
            }
        }
        return maxSum;
    }
}

#include <vector>

using namespace std;

int maxQueenSum(vector<vector<int>>& board) {
    vector<int> rowsSum(board.size(), 0);
    vector<int> colsSum(board[0].size(), 0);
    vector<int> d1Sum(board.size() + board[0].size() - 1, 0);
    vector<int> d2Sum(board.size() + board[0].size() - 1, 0);

    // предподсчет сумм строк, столбцов и диагоналей
    for (int i = 0; i < board.size(); ++i) {
        for (int j = 0; j < board[i].size(); ++j) {
            int val = board[i][j];
            rowsSum[i] += val;
            colsSum[j] += val;
            d1Sum[(board.size() - 1 - i) + j] += val;
            d2Sum[i + j] += val;
        }
    }

    int maxSum = 0;
    for (int i = 0; i < board.size(); ++i) {
        for (int j = 0; j < board[i].size(); ++j) {
            // сумма строки, столбца и двух диагоналей
            // минус 3x серединный элемент (он посчитан 4 раза)
            int currSum = rowsSum[i] + colsSum[j];
            currSum += d1Sum[(board.size() - 1 - i) + j] + d2Sum[i + j];
            currSum -= 3 * board[i][j];

            if (i == 0 && j == 0) {
                maxSum = currSum;
            }
            maxSum = max(maxSum, currSum);
        }
    }
    return maxSum;
}

package main

func maxQueenSum(board [][]int) int {
    rowsSum := make([]int, len(board))
    colsSum := make([]int, len(board[0]))
    d1Sum := make([]int, len(board)+len(board[0])-1)
    d2Sum := make([]int, len(board)+len(board[0])-1)

    // предподсчет сумм строк, столбцов и диагоналей
    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[i]); j++ {
            val := board[i][j]
            rowsSum[i] += val
            colsSum[j] += val
            d1Sum[(len(board)-1-i)+j] += val
            d2Sum[i+j] += val
        }
    }

    maxSum := 0
    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[i]); j++ {
            // сумма строки, столбца и двух диагоналей
            // минус 3x серединный элемент (он посчитан 4 раза)
            currSum := rowsSum[i] + colsSum[j]
            currSum += d1Sum[(len(board)-1-i)+j] + d2Sum[i+j]
            currSum -= 3 * board[i][j]

            if i == 0 && j == 0 {
                maxSum = currSum
            }
            if currSum > maxSum {
                maxSum = currSum
            }
        }
    }
    return maxSum
}

import java.util.*;

public class Solution {
    public int maxQueenSum(List<List<Integer>> board) {
        int[] rowsSum = new int[board.size()];
        int[] colsSum = new int[board.get(0).size()];
        int[] d1Sum = new int[board.size() + board.get(0).size() - 1];
        int[] d2Sum = new int[board.size() + board.get(0).size() - 1];

        // предподсчет сумм строк, столбцов и диагоналей
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board.get(i).size(); j++) {
                int val = board.get(i).get(j);
                rowsSum[i] += val;
                colsSum[j] += val;
                d1Sum[(board.size() - 1 - i) + j] += val;
                d2Sum[i + j] += val;
            }
        }

        int maxSum = 0;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board.get(i).size(); j++) {
                // сумма строки, столбца и двух диагоналей
                // минус 3x серединный элемент (он посчитан 4 раза)
                int currSum = rowsSum[i] + colsSum[j];
                currSum += d1Sum[(board.size() - 1 - i) + j] + d2Sum[i + j];
                currSum -= 3 * board.get(i).get(j);

                if (i == 0 && j == 0) {
                    maxSum = currSum;
                }
                maxSum = Math.max(maxSum, currSum);
            }
        }
        return maxSum;
    }
}

import java.util.*;

public class Solution {
    public int maxQueenSum(List<List<Integer>> board) {
        int[] rowsSum = new int[board.size()];
        int[] colsSum = new int[board.get(0).size()];
        int[] d1Sum = new int[board.size() + board.get(0).size() - 1];
        int[] d2Sum = new int[board.size() + board.get(0).size() - 1];

        // предподсчет сумм строк, столбцов и диагоналей
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board.get(i).size(); j++) {
                int val = board.get(i).get(j);
                rowsSum[i] += val;
                colsSum[j] += val;
                d1Sum[(board.size() - 1 - i) + j] += val;
                d2Sum[i + j] += val;
            }
        }

        int maxSum = 0;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board.get(i).size(); j++) {
                // сумма строки, столбца и двух диагоналей
                // минус 3x серединный элемент (он посчитан 4 раза)
                int currSum = rowsSum[i] + colsSum[j];
                currSum += d1Sum[(board.size() - 1 - i) + j] + d2Sum[i + j];
                currSum -= 3 * board.get(i).get(j);

                if (i == 0 && j == 0) {
                    maxSum = currSum;
                }
                maxSum = Math.max(maxSum, currSum);
            }
        }
        return maxSum;
    }
}

from typing import *

def max_queen_sum(board: List[List[int]]) -> int:
    # rows_sum[i] - сумма элементов i-ой строки
    rows_sum = [0] * len(board)
    # cols_sum[i] - сумма элементов i-ой колонки
    cols_sum = [0] * len(board[0])
    # суммы элементов на диагоналях
    d1_sum = [0] * (len(board) + len(board[0]) - 1)
    d2_sum = [0] * (len(board) + len(board[0]) - 1)

    # предподсчет сумм строк, столбцов и диагоналей
    for i in range(len(board)):
        for j in range(len(board[i])):
            val = board[i][j]
            rows_sum[i] += val
            cols_sum[j] += val
            d1_sum[(len(board) - 1 - i) + j] += val
            d2_sum[i + j] += val

    max_sum = 0
    for i in range(len(board)):
        for j in range(len(board[i])):
            # сумма строки, столбца и двух диагоналей
            # минус 3x серединный элемент (он посчитан 4 раза)
            curr_sum = rows_sum[i] + cols_sum[j]
            curr_sum += d1_sum[(len(board) - 1 - i) + j] + d2_sum[i + j]
            curr_sum -= 3 * board[i][j]

            if i == 0 and j == 0:
                max_sum = curr_sum
            max_sum = max(max_sum, curr_sum)
    return max_sum

Оценка сложности

Время: O(n * m), где n - число строк, m - число столбцов в board
Память: O(n + m), где n - число строк, m - число столбцов в board