999 可以被一步捕获的棋子数

题目链接

999. 可以被一步捕获的棋子数

分析

水题水做

找到车的位置，直接模拟向四个方向走，碰到的第一个棋子是卒即答案+1

代码实现

class Solution {
public:
    int numRookCaptures(vector<vector<char>>& board) {
        vector<pair<int, int>> dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        auto check = [](int x, int y) -> bool {return x >= 0 && x < 8 && y >= 0 && y < 8;};
        int ans = 0;
        for(int x = 0; x < 8; ++x)
        {
            for(int y = 0; y < 8; ++y)
            {
                if(board[x][y] == 'R')
                {
                    for(auto& [dx, dy] : dir)
                    {
                        int tx = x + dx, ty = y + dy;
                        while(check(tx, ty) && board[tx][ty] == '.')
                            tx += dx, ty += dy;
                        if(check(tx, ty) && board[tx][ty] == 'p')
                            ans++;
                    }
                }
            }
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：$O(S^2)$，其中 $S$ 为棋盘的大小
• 空间复杂度：$O(1)$