一.题目描述
NC518下象棋
牛妹在和牛牛下牛客象棋。现在轮到牛妹了，牛妹想知道她在这一回合能否战胜牛牛。
棋盘chessboard上只可能包含：炮，将，车，兵
牛客象棋的规则解释：
炮：炮在不吃子的时候，走动与车完全相同，但炮在吃棋子时，必须跳过一个棋子，我方的和敌方的都可以
兵：可以上下左右移动，每次只能移动一格
车：上下左右均可走，只要无棋子阻拦，步数不受限制。
将：可以上下左右移动，每次只能移动一格
接下来给出一个棋盘，牛妹的棋子用大写字母表示，牛牛的棋子用小写字母表示。
将用J,j表示，炮用P,p表示，车用C,c表示，兵用B,b表示，没有棋子的格子用.表示保证棋盘上一定同时包含J与j各一个。牛妹能胜利则返回"Happy"，否则返回"Sad"
二.算法(模拟)
对于该题我们首先要明白题目是在着一回合下能否战胜牛牛，也就是牛妹能不能再这一回合将军(吃掉牛牛的将)。对于兵、车和将我们都能理解，但是这个炮我们需要注意一样，该题目是要求跳过一个棋子，并不是按照象棋规则那样。
图片说明
对于上面牛妹战胜牛牛的几种情况，我们可以进行模拟。我们首先遍历找到牛牛的将的位置，然后反向推出是否可以满足上述的情况，进而判断是不是可以胜利，下面是完整代码：

class Solution {
public:
    string playchess(vector<string>& chessboard) {
        //方向数组，上下左右四个方位
        int dx[]={0,-1,1,0};
        int dy[]={-1,0,0,1};
        //n,m分别表示棋盘的长和宽
        int n=chessboard.size();
        int m=chessboard[0].size();
        int x=0,y=0;
        for(int i=0;i<chessboard.size();i++){
            for(int j=0;j<chessboard[0].size();j++){
                if(chessboard[i][j]=='j'){
                    x=i;
                    y=j;
                    //(x,y)表示牛牛的将的位置
                    break;
                }
            }
        }
        for(int k=0;k<4;k++){
            //对每一个相邻位置进行判断
            int nx=x+dx[k];
            int ny=y+dy[k];
            bool ck=true;//判断当前位置是否和牛牛将相邻
            int cnt=0;//和牛牛将中间隔了多少棋子
            while(nx>=0&&nx<n&&ny>=0&&ny<m){
                //旁边有牛妹的将或者是兵 牛妹就之间胜利
                if((chessboard[nx][ny]=='B'||chessboard[nx][ny]=='J')&&ck){
                    return "Happy";
                }
                if(chessboard[nx][ny]=='P'&&cnt==1) return "Happy";
                if(chessboard[nx][ny]=='C'&&cnt==0) return "Happy";
                //此时已经不是相邻位置了 所以ck=false
                ck=false;
                if(chessboard[nx][ny]!='.'){
                    cnt++;
                }
                if(cnt>1) break;
                //下一个位置进行搜索
                nx+=dx[k];
                ny+=dy[k];
            }
        }
        return "Sad";
    }
};

时间复杂度：其中n,m分别表示棋盘的长和宽。
空间复杂度：没有使用其他额外空间
优缺点：思路简单，但是实现起来麻烦

三.算法(模拟+java实现)
首先找到牛牛的将在什么位置。分四种情况进行讨论，看牛牛是否能用兵、将、车、炮中得某一种赢得胜利，只要满足其中之一，就返回"Happy"，否则返回"Sad"。
以牛牛将的位置为起点，沿着四个方向进行搜索，当与起点位置相邻
(1)当前位置是牛妹的兵时，说明牛妹可以赢，直接返回"Happy";
(2)当与起点位置相邻，并且当前位置是牛妹的将时，说明牛妹可以赢，直接返回"Happy";
(3)当与起点位置之间的棋子数为0个，并且当前位置是牛妹的车时，说明牛妹可以赢，直接返回"Happy";
(4)当与起点位置之间的棋子数只有一个，并且当前位置是牛妹的炮时，说明牛妹可以赢，直接返回"Happy"。
下面是完整代码：

import java.util.*;
public class Solution {
public String playchess (String[] chessboard) {
        int n = chessboard.length;
        int m = chessboard[0].length();
        // 将String类转换为字符数组 方便处理
        char[][] board = new char[n][m];
        for (int i=0;i<n;i++){
            board[i] = chessboard[i].toCharArray();
        }
        // 当前位置的上下左右
        int dx[]={-1,0,1,0};
        int dy[]={0,1,0,-1};
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                // 发现牛牛的将的位置
                if (board[i][j] == 'j'){
                    // 判断牛牛将上下左右各方方向上的棋子，利用l更新牛牛将上（下左右）方第几个格子
                    for(int k=0;k<4;k++){
                        //对每一个相邻位置进行判断
                        int nx=i+dx[k];
                        int ny=j+dy[k];
                        boolean ck=true;//判断当前位置是否和牛牛将相邻
                        int cnt=0;//和牛牛将中间隔了多少棋子
                        while(nx>=0&&nx<n&&ny>=0&&ny<m){
                        //旁边有牛妹的将或者是兵 牛妹就之间胜利
                        if((board[nx][ny]=='B'||board[nx][ny]=='J')&&ck) return "Happy";
                        if(board[nx][ny]=='P'&&cnt==1) return "Happy";
                        if(board[nx][ny]=='C'&&cnt==0) return "Happy";
                        //此时已经不是相邻位置了 所以ck=false
                        ck=false;
                        if(board[nx][ny]!='.') cnt++;
                        if(cnt>1) break;
                        //下一个位置进行搜索
                        nx+=dx[k];
                        ny+=dy[k];
                       }
                     }
                 }
            }
        }
        return "Sad";
    }
}

时间复杂度：其中n,m分别表示棋盘的长和宽。
空间复杂度：没有使用其他额外空间
优缺点：思路和算法二思路差不多，但是感觉写起来相比于c++麻烦一点