[leetcode] 999. Available Captures for Rook

[leetcode] 999. Available Captures for Rook

Description

Given an integer array with even length, where different numbers On an 8 x 8 chessboard, there is one white rook. There also may be empty squares, white bishops, and black pawns. These are given as characters ‘R’, ‘.’, ‘B’, and ‘p’ respectively. Uppercase characters represent white pieces, and lowercase characters represent black pieces.

The rook moves as in the rules of Chess: it chooses one of four cardinal directions (north, east, west, and south), then moves in that direction until it chooses to stop, reaches the edge of the board, or captures an opposite colored pawn by moving to the same square it occupies. Also, rooks cannot move into the same square as other friendly bishops.

Return the number of pawns the rook can capture in one move.

Example 1:

Input: [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]Output: 3Explanation: In this example the rook is able to capture all the pawns.

Example 2:

Input: [[".",".",".",".",".",".",".","."],[".","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",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]Output: 0Explanation: Bishops are blocking the rook to capture any pawn.

Example 3:

Input: [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","p",".",".",".","."],["p","p",".","R",".","p","B","."],[".",".",".",".",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."]]Output: 3Explanation: The rook can capture the pawns at positions b5, d6 and f5.

Note:

board.length == board[i].length == 8board[i][j] is either ‘R’, ‘.’, ‘B’, or ‘p’There is exactly one cell with board[i][j] == ‘R’

分析

题目的意思是：这道题就是看R周围有多少个p（东南西北方向），如果一个p被p或者B挡着的话就不能算，这样的话最高只有4个了。解答过程也是简单粗暴，把R的位置找到，然后再遍历R的四周有多少个p，即每遍历一个p，就判断p是否符合要求，即要在同一行或者同一列，并且中间没有其他的p和B。代码就简单粗暴直接把这四种情况写出来了哈，也AC了，哈哈

写完了之后我想到了第二种解法，找到R的位置之后，只需要遍历当前R位置的所在的行或者列有没有R或者B就行了，看来还是有更优的解法了

代码

class Solution: def numRookCaptures(self, board: List[List[str]]) -> int: m=len(board) n=len(board[0]) R_row=0 R_col=0 for i in range(m): for j in range(n): if(board[i][j]=='R'): R_row=i R_col=j break cnt=0 for i in range(m): for j in range(n): if(board[i][j]=='p'): flag=True if(i==R_row and jR_col): for p in range(j-1,R_col,-1): if(board[i][p]=='B' or board[i][p]=='p'): flag=False break elif(j==R_col and iR_row): for p in range(i-1,R_row,-1): if(board[p][j]=='B' or board[p][j]=='p'): flag=False break else: continue if(flag): cnt+=1 return cnt

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。