题解 | #下象棋#

下象棋

http://www.nowcoder.com/practice/2b0f51e8b1594d7091576dab05e00693

题目描述

棋盘中包含四种棋子:炮P、将J、车C、兵B
牛妹棋子用大写字母表示,牛牛棋子用小写字母表示
问一回合内牛妹能否战胜牛牛

方法一模拟

解题思路

棋子只能吃掉与自己同一行或同一列的棋子，所以可以只考虑与牛牛的将同一行或同一列的棋子。
对于牛妹的兵和将，需要位于牛牛的将上下左右四个相邻的位置；对于牛妹的车，与牛牛的将之间不能有其棋子；对于牛妹的炮，与牛牛的将之间有且只有一个棋子。
对于兵和将，要想获胜，需要：
图片说明

对于车，要想获胜，需要：
图片说明

对于炮，要想获胜，需要：
图片说明

按照上述规则，检查与j同一行和同一列的棋子即可。

代码示例

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param chessboard string字符串vector 
     * @return string字符串
     */
    string playchess(vector<string>& chessboard) {
        // n，m表示chessboard的大小
        int n = chessboard.size(), m = chessboard[0].size();
        vector<vector<int>>dir = { {0,-1},{0,1},{-1,0},{1,0} };
        // 遍历棋盘，找到j所在的位置
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                // 找到了j的位置
                if (chessboard[i][j] == 'j')
                {
                    // 用变量k来遍历j的四个方向
                    for (int k = 0; k < 4; k++)
                        // nx，ny为与牛牛同一行或同一列的坐标位置
                        // cnt初始为0，用来记录棋盘中[nx,ny]与[i,j]之间棋子的个数（用于车和炮的判断）
                        // l用来记录与牛牛的将的距离（用于兵和将的判断）
                        for (int cnt = 0, nx = i + dir[k][0], ny = j + dir[k][1], l = 2;
                             nx >= 0 && nx < n && ny >= 0 && ny < m;
                             nx = i + dir[k][0] * l, ny = j + dir[k][1] * l, l++)
                        {
                            // 如果遍历到的位置是牛妹的棋子，根据条件判断是否能取胜
                            // 兵和将：与牛妹的将必须相邻，即l==2
                            // 炮：与牛妹的将之间有一个棋子，即cnt==1
                            // 车：与牛妹的将之间没有棋子，即cnt==0
                            if (((chessboard[nx][ny] == 'B' || chessboard[nx][ny] == 'J') && l == 2)
                                || (chessboard[nx][ny] == 'P' && cnt == 1) || (chessboard[nx][ny] == 'C' && !cnt))
                                return "Happy";
                            cnt += chessboard[nx][ny] != '.';
                            // 与牛牛的将之间至少两个棋子，不可能获胜
                            if (cnt > 1)
                                break;
                        }
                    break;
                }
        return "Sad";
    }
};

复杂度分析

时间复杂度：需要先遍历一遍棋盘，找到牛牛将的位置， $O(n*m)$ 。找到牛牛将的位置之后，需要遍历一行和一列，时间复杂度为 $O(n+m)$ 。所以总的时间复杂度为 $O(n*m)$
空间复杂度：使用了常数个变量，空间复杂度为 $O(1)$

方法二分类讨论

解题思路

方法一是以牛牛的将为中心进行模拟，还可以以牛妹的棋子为中心进行模拟。
具体来说，我们只需要对牛妹的每个棋子判断其能否吃掉牛牛的将，如果都吃不掉，那么牛妹便此回合不能获胜，否则牛妹此回合可以获胜。
具体规则与方法一一样：
对于牛妹的兵和将，需要位于牛牛的将上下左右四个相邻的位置；对于牛妹的车，与牛牛的将之间不能有其棋子；对于牛妹的炮，与牛牛的将之间有且只有一个棋子。
可以考虑使用两个pair存储棋子种类和棋子的x、y坐标，在对行和列遍历时，可以根据这两个数组快速进行判断。以对行遍历为例，如果棋子是P，那么需要查询与P相隔一个棋子的棋子是否为j；如果棋子是J/B，那么需要查询该棋子邻居是否为j，并且距离为1；如果棋子为C，那么仅需要查询该棋子邻居是否为j。例如，对于下述棋盘，
图片说明
棋子种类及其x、y坐标为：

代码示例

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param chessboard string字符串vector 
     * @return string字符串
     */
    string playchess(vector<string>& chessboard) {
        // n，m为chessboard的大小
        int n=chessboard.size(), m=chessboard[0].size();
        // 存储棋子种类和它的x，y坐标
        vector<pair<char,int>> x[n+1],y[m+1];
        // 存储棋子种类和它的x坐标
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(chessboard[i-1][j-1]!='.')
                    x[i].push_back({chessboard[i-1][j-1],j});
        // 存储棋子种类和它的y坐标
        for(int j=1;j<=m;j++)
             for(int i=1;i<=n;i++)
                if(chessboard[i-1][j-1]!='.')
                    y[j].push_back({chessboard[i-1][j-1],i});
        // fg==0：不能获胜；fg==1，可以获胜
        int fg=0;
        // 遍历每一行
        for(int i=1;i<=n;i++) {
            // 取出所有棋子及其x坐标
            for(int j=0;j<x[i].size();j++) {
                char ch=x[i][j].first;
                // 棋子是炮
                if(ch=='P') {
                    // 棋子相隔一个棋子的棋子是牛牛的将
                    if(j-2>=0&&x[i][j-2].first=='j') fg=1;
                    if(j+2<x[i].size()&&x[i][j+2].first=='j') fg=1;
                }
                // 棋子是兵或将
                if(ch=='B'||ch=='J') {
                    // 与牛牛的将相邻，距离为1
                    if(j-1>=0&&x[i][j-1].first=='j'&&abs(x[i][j-1].second-x[i][j].second)==1) fg=1;
                    if(j+1<x[i].size()&&x[i][j+1].first=='j'&&abs(x[i][j+1].second-x[i][j].second)==1) fg=1;
                }
                // 棋子是车
                if(ch=='C') {
                    // 与牛牛的将之间没有棋子
                    if(j-1>=0&&x[i][j-1].first=='j') fg=1;
                    if(j+1<x[i].size()&&x[i][j+1].first=='j') fg=1;
                }
            }
        }
        // 遍历每一列
        for(int i=1;i<=m;i++) {
            for(int j=0;j<y[i].size();j++) {
                char ch=y[i][j].first;
                // 棋子是炮
                if(ch=='P') {
                    // 棋子相隔一个棋子的棋子是牛牛的将
                    if(j-2>=0&&y[i][j-2].first=='j') fg=1;
                    if(j+2<y[i].size()&&y[i][j+2].first=='j') fg=1;
                }
                // 棋子是兵或将
                if(ch=='B'||ch=='J') {
                    // 与牛牛的将相邻，距离为1
                    if(j-1>=0&&y[i][j-1].first=='j'&&abs(y[i][j-1].second-y[i][j].second)==1) fg=1;
                    if(j+1<y[i].size()&&y[i][j+1].first=='j'&&abs(y[i][j+1].second-y[i][j].second)==1) fg=1;
                }
                // 棋子是车
                if(ch=='C') {
                    // 与牛牛的将之间没有棋子
                    if(j-1>=0&&y[i][j-1].first=='j') fg=1;
                    if(j+1<y[i].size()&&y[i][j+1].first=='j') fg=1;
                }
            }
        }
        if(fg) return "Happy";
        else return "Sad";
    }
};