ການຈັບພາບທີ່ມີຢູ່ ສຳ ລັບການແກ້ໄຂ Rook Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Square
Array

ຖະແຫຼງການບັນຫາ

ໃນບັນຫານີ້, ພວກເຮົາໄດ້ຮັບຕາຕະລາງ 2-D ທີ່ເປັນຕົວແທນຂອງກ chessboard ມີ rook ສີຂາວ ແລະຊິ້ນສ່ວນອື່ນໆໃສ່ມັນ. Rook ຂອງ White ແມ່ນສະແດງໂດຍຕົວລະຄອນ 'R'. ອະທິການຂອງສີຂາວແມ່ນຕົວແທນໂດຍ 'ບ' ແລະ ໝູ ດຳ ແມ່ນເປັນຕົວແທນ 'p'. ບັນຫາຮັບປະກັນວ່າບໍ່ມີສິ້ນອື່ນນອກ ເໜືອ ຈາກທີ່ກ່າວມາຂ້າງເທິງ. ເປົ້າ ໝາຍ ຂອງພວກເຮົາແມ່ນເພື່ອຊອກຫາ ຈຳ ນວນປາຄໍ່ສີ ດຳ ທີ່ເປັນໄປໄດ້ເຊິ່ງສາມາດຈັບໄດ້ໂດຍ ໝາ ສີຂາວໃນການເຄື່ອນໄຫວ ໜຶ່ງ ຄັ້ງ (ພິຈາລະນາກົດລະບຽບຂອງ ໝາກ ຮຸກທົ່ວໄປ).

ຍົກຕົວຢ່າງ

board = [[".",".",".",".",".",".",".","."],
         [".",".",".","p",".",".",".","."],
         [".",".",".","R",".",".",".","p"],
         [".",".",".",".",".",".",".","."],
         [".",".",".",".",".",".",".","."],
         [".",".",".","p",".",".",".","."],
         [".",".",".",".",".",".",".","."],
         [".",".",".",".",".",".",".","."]]
3
board = [[".",".",".",".",".",".",".","."],
         [".","p","p","p","p","p",".","."],
         [".","p","p","B","p","p",".","."],
         [".","p","B","R","B","p",".","."],
         [".","p","p","B","p","p",".","."],
         [".","p","p","p","p","p",".","."],
         [".",".",".",".",".",".",".","."],
         [".",".",".",".",".",".",".","."]]
0

ຄໍາອະທິບາຍ

ການຈັບພາບທີ່ມີຢູ່ ສຳ ລັບການແກ້ໄຂ Rook Leetcode

ວິທີການ

ວິທີການ ສຳ ລັບບັນຫາແມ່ນການຊອກຫາ ຕຳ ແໜ່ງ ຂອງ rook ໃນ chessboard 2-D ທຳ ອິດ array ແລະຫຼັງຈາກນັ້ນພວກເຮົາສາມາດກວດສອບຕາມທິດທາງເທິງ, ເບື້ອງຊ້າຍ, ຂວາແລະລຸ່ມເພື່ອຊອກຫາວ່າພວກເຮົາສາມາດຊອກຫາ ໜອງ ປາ ດຳ ('p'). ໃນກໍລະນີ, ພວກເຮົາໄປຮອດຈຸດສຸດທ້າຍຫຼືປະທ້ວງອະທິການທີ່ມີສີດຽວກັນໃນທິດທາງໃດ ໜຶ່ງ, ພວກເຮົາຢຸດກວດກາເບິ່ງທິດທາງນັ້ນຕື່ມອີກ.

ລະບົບວິເຄາະ

  1. ລອກຕາຕະລາງທັງ ໝົດ ເພື່ອຊອກຫາຕົວອັກສອນ 'R' ແລະບັນທຶກແຖວແລະຖັນຂອງມັນໄວ້ໃນ r, ຄ ຕາມລໍາດັບ.
  2. ເລີ່ມຕົ້ນ cnt ເພື່ອເກັບຮັກສາ ຈຳ ນວນປາທີ່ສາມາດຈັບໄດ້
  3. ກວດເບິ່ງໃນທິດທາງເທິງ, ຊ່ວງ: i ∈ (0, r - 1):
      • if ກະດານ [i] [ຄ] == 'p':
        • ການເພີ່ມຂື້ນ cnt, cnt ++
        • ພັກຜ່ອນ
      • if ກະດານ [i] [ຄ] == 'ຂ':
        • ພັກຜ່ອນ
  4. ເຮັດແບບດຽວກັນກັບເບື້ອງຊ້າຍ, ຂວາແລະທິດທາງລຸ່ມ
  5. Return cnt

ການປະຕິບັດຂອງການຈັບທີ່ມີຢູ່ສໍາລັບການແກ້ໄຂ Rook Leetcode

ໂຄງການ C ++

#include <bits/stdc++.h>

using namespace std;

int numRookCaptures(vector<vector<char>>& board)
{
    if(board.empty())
        return 0;
    int n = board.size() , m = board[0].size() , cnt = 0 , r , c;

    for(int i = 0 ; i < n ; i++)
        for(int j = 0 ; j < m ; j++)
        {
            if(board[i][j] == 'R')
            {
                r = i;
                c = j;
                break;
            }
        }


    for(int i = r - 1 ; i >= 0 ; i--)
    {
        if(board[i][c] == 'p')
        {
            cnt++;
            break;
        }
        if(board[i][c] == 'B')
            break;
    }
    for(int i = r + 1 ; i < n ; i++)
    {
        if(board[i][c] == 'p')
        {
            cnt++;
            break;
        }
        if(board[i][c] == 'B')
            break;
    }

    for(int j = c - 1 ; j >= 0 ; j--)
    {
        if(board[r][j] == 'p')
        {
            cnt++;
            break;
        }
        if(board[r][j] == 'B')
            break;
    }

    for(int j = c + 1 ; j < m ; j++)
    {
        if(board[r][j] == 'p')
        {
            cnt++;
            break;
        }
        if(board[r][j] == 'B')
            break;
    }
    return cnt;
}

int main() {
    vector <vector <char> > board = {{'.','.','.','.','.','.','.','.'},
                                    {'.','.','.','p','.','.','.','.'},
                                    {'.','.','.','R','.','.','.','p'},
                                    {'.','.','.','.','.','.','.','.'},
                                    {'.','.','.','.','.','.','.','.'},
                                    {'.','.','.','p','.','.','.','.'},
                                    {'.','.','.','.','.','.','.','.'},
                                    {'.','.','.','.','.','.','.','.'}};


    cout << numRookCaptures(board) << endl;
    return 0;
}

Java Program

class number_of_rook_captures {

    public static void main(String args[]) {
        char[][] board = {{'.','.','.','.','.','.','.','.'},
                         {'.','.','.','p','.','.','.','.'},
                         {'.','.','.','R','.','.','.','p'},
                         {'.','.','.','.','.','.','.','.'},
                         {'.','.','.','.','.','.','.','.'},
                         {'.','.','.','p','.','.','.','.'},
                         {'.','.','.','.','.','.','.','.'},
                         {'.','.','.','.','.','.','.','.'}};

        System.out.println(numRookCaptures(board));
    }

    public static int numRookCaptures(char [][] board) {
        if(board.length == 0)
            return 0;
        int n = board.length , m = board[0].length , cnt = 0 , r = -1 , c = -1;

        for(int i = 0 ; i < n ; i++)
            for(int j = 0 ; j < m ; j++)
            {
                if(board[i][j] == 'R')
                {
                    r = i;
                    c = j;
                    break;
                }
            }


        for(int i = r - 1 ; i >= 0 ; i--)
        {
            if(board[i][c] == 'p')
            {
                cnt++;
                break;
            }
            if(board[i][c] == 'B')
                break;
        }
        for(int i = r + 1 ; i < n ; i++)
        {
            if(board[i][c] == 'p')
            {
                cnt++;
                break;
            }
            if(board[i][c] == 'B')
                break;
        }

        for(int j = c - 1 ; j >= 0 ; j--)
        {
            if(board[r][j] == 'p')
            {
                cnt++;
                break;
            }
            if(board[r][j] == 'B')
                break;
        }

        for(int j = c + 1 ; j < m ; j++)
        {
            if(board[r][j] == 'p')
            {
                cnt++;
                break;
            }
            if(board[r][j] == 'B')
                break;
        }
        return cnt;
    }
}
3

ການວິເຄາະຄວາມສັບສົນຂອງການຈັບຕົວທີ່ມີຢູ່ ສຳ ລັບການແກ້ໄຂ Rook Leetcode

ຄວາມສັບສົນເວລາ

O (1), ດັ່ງທີ່ພວກເຮົາ iterate ຈໍານວນຄົງທີ່ຂອງເວລາ.

ຄວາມສັບສົນໃນອະວະກາດ

O (1), ດັ່ງທີ່ພວກເຮົາໃຊ້ພຽງແຕ່ພື້ນທີ່ ໜ່ວຍ ຄວາມ ຈຳ ຄົງທີ່ໂດຍບໍ່ ຄຳ ນຶງເຖິງວັດສະດຸປ້ອນ.