下象棋题解_牛客博客

题解1：AC
逆向思维思考，因为所有棋子都只能上下左右移动，所以为了判断牛牛的将能否被吃下，只需要判断牛牛的那一行与列的棋子情况即可。
具体来说：对于兵和将，只可能在牛牛的将的上下左右四个相邻的方向上才能取胜；
对于车来说，只可能在上下左右四个方向上并且与牛牛的将之间没有其他棋子时才能取胜；对于炮来说，只可能在上下左右四个方向上并且与牛牛的将之间有且仅有一个其他棋子时才能取胜。
所以我们可以扫描牛牛的将所在的位置，再对那一行一列进行判断。时间复杂度O(n*m)，空间复杂度O(1)。

class Solution {
public:
    /**
     *
     * @param chessboard string字符串vector
     * @return string字符串
     */
    string playchess(vector<string>& chessboard) {
        // write code here
        int n = chessboard.size(), m = chessboard[0].size();
        vector<vector<int>>dir = { {0,-1},{0,1},{-1,0},{1,0} };
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (chessboard[i][j] == 'j')
                {
                    for (int k = 0; k < 4; k++)
                        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++)
                        {
                            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";
    }
};

题解2：AC
模拟即可，只需要分别判断牛妹的炮，将，兵，车能否攻下牛牛的将。
具体来说：对于兵和将，只可能在牛牛的将的上下左右四个相邻的方向上才能取胜；
对于车来说，只可能在上下左右四个方向上并且与牛牛的将之间没有其他棋子时才能取胜；对于炮来说，只可能在上下左右四个方向上并且与牛牛的将之间有且仅有一个其他棋子时才能取胜。
对地图分别按照 $x$ 轴与 $y$ 轴进行了离散化，对于每一个 $x$ 与 $y$ 存储了他这一行/一列的棋子信息，然后只需要分别遍历离散化后 $x$ 轴与 $y$ 轴数组，看看每一类棋子能否攻下牛牛的将即可。时间复杂度 $O(n*m)$ ,空间复杂度 $O(n*m)$

class Solution {
public:
    /**
     * 
     * @param chessboard string字符串vector 
     * @return string字符串
     */
    string playchess(vector<string>& chessboard) {
        // write code here
        int n=chessboard.size();
        int m=chessboard[0].size();
        vector<pair<char,int>>x[n+1],y[m+1];
        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});
        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});
        int fg=0;
        for(int i=1;i<=n;i++) {
            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') {
                    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') {
                    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";
    }
};