题解 | #下象棋#

题意整理

只要牛妹的炮，将，车，兵的任意一个能吃到牛牛的将，则牛妹获胜。
将、兵只有在相邻的时候才能吃。
炮、车在同行和同列都可以吃，炮需要隔一个棋子，车不能有棋子挡在中间。

方法一（模拟搜索）

1.解题思路

首先找到牛牛的将在什么位置。
以牛牛将的位置为起点，沿着四个方向进行搜索，当与起点位置相邻，并且当前位置是牛妹的将或兵时，说明牛妹可以赢，直接返回"Happy";当与起点位置之间的棋子数为0个，并且当前位置是牛妹的车时，说明牛妹可以赢，直接返回"Happy"；当与起点位置之间的棋子数只有一个，并且当前位置是牛妹的炮时，说明牛妹可以赢，直接返回"Happy"。
最后，如果没有找到赢得情况，返回"Sad"。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param chessboard string字符串一维数组 
     * @return string字符串
     */
    public String playchess (String[] chessboard) {
        //计算棋盘的长和宽
        int m=chessboard.length;
        int n=chessboard[0].length();
        //定义搜索的方向
        int[][] directions={{-1,0},{0,-1},{1,0},{0,1}};
        //记录牛牛的将所在位置        
        int x=0,y=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                //找到牛牛的将所在位置
                if(chessboard[i].charAt(j)=='j'){
                    x=i;
                    y=j;
                    break;
                }
            }
        }

        //向左下右上四个方向搜索
        for(int k=0;k<4;k++){
            //搜索的第一个位置
            int nx=x+directions[k][0];
            int ny=y+directions[k][1];
            //是否与将相邻
            boolean neighbor=true;
            //与将的中间隔了多少个棋子
            int cnt=0;
            //保证位置在棋盘内
            while(nx>=0&&nx<m&&ny>=0&&ny<n){
                if(((chessboard[nx].charAt(ny)=='B'||chessboard[nx].charAt(ny)=='J')&&neighbor)
                   ||((chessboard[nx].charAt(ny)=='P')&&cnt==1)
                   ||((chessboard[nx].charAt(ny)=='C')&&cnt==0)){
                    return "Happy";
                }
                neighbor=false;
                if(chessboard[nx].charAt(ny)!='.'){
                    cnt++;
                }
                //如果障碍棋子超过2，直接终止搜索
                if(cnt>1){
                    break;
                }
                //下一个位置
                nx+=directions[k][0];
                ny+=directions[k][1];
            }
        }
        return "Sad";
    }
}

3.复杂度分析

时间复杂度：寻找牛牛将的时候，最多循环 $图片说明$ 次，沿四个方向搜索的时候，最多循环 $图片说明$ 次，所以时间复杂度是 $图片说明$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $图片说明$ 。

方法二（分情况讨论）

1.解题思路

首先找到牛牛的将在什么位置。
分四种情况进行讨论，看牛牛是否能用兵、将、车、炮中得某一种赢得胜利，只要满足其中之一，就返回"Happy"，否则返回"Sad"。
以牛牛将的位置为起点，沿着四个方向进行搜索，当与起点位置相邻，并且当前位置是牛妹的兵时，说明牛妹可以赢，直接返回"Happy";当与起点位置相邻，并且当前位置是牛妹的将时，说明牛妹可以赢，直接返回"Happy";当与起点位置之间的棋子数为0个，并且当前位置是牛妹的车时，说明牛妹可以赢，直接返回"Happy"；当与起点位置之间的棋子数只有一个，并且当前位置是牛妹的炮时，说明牛妹可以赢，直接返回"Happy"。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param chessboard string字符串一维数组 
     * @return string字符串
     */
    //声明棋盘数组、长、宽以及牛牛将所在位置
    private char[][] chess;
    private int x,y,m,n;


    public String playchess (String[] chessboard) {
        //计算棋盘的长和宽
        m=chessboard.length;
        n=chessboard[0].length();
        //定义二维字符数组，存放棋子
        chess=new char[m][n];
        //初始化牛牛的将所在位置
        x=0;
        y=0;
        //查找牛牛的将，并将所有棋子转移到chess数组
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                chess[i][j]=chessboard[i].charAt(j);
                if(chess[i][j]=='j'){
                    x=i;
                    y=j;
                }
            }
        }

        return (winBySoldier()||winByGeneral()||winByCarriage()||winByGun())?"Happy":"Sad";

    }

    //判断牛妹是否能用兵取得胜利
    private boolean winBySoldier(){
        boolean win=false;
        if(x>0&&chess[x-1][y]=='B'){
            win=true;
        }
        if(x<m-1&&chess[x+1][y]=='B'){
            win=true;
        }
        if(y>0&&chess[x][y-1]=='B'){
            win=true;
        }
        if(y<n-1&&chess[x][y+1]=='B'){
            win=true;
        }
        return win;
    }

    //判断牛妹是否能用将取得胜利
    private boolean winByGeneral(){
        boolean win=false;
        if(x>0&&chess[x-1][y]=='J'){
            win=true;
        }
        if(x<m-1&&chess[x+1][y]=='J'){
            win=true;
        }
        if(y>0&&chess[x][y-1]=='J'){
            win=true;
        }
        if(y<n-1&&chess[x][y+1]=='J'){
            win=true;
        }
        return win;
    }

    //判断牛妹是否能用车取得胜利
    private boolean winByCarriage(){
        boolean win=false;
        for(int i=0;i<m;i++){
            //同一列上是否有车
            if(chess[i][y]=='C'){
                boolean barrier=false;
                if(i>x){
                    for(int k=x+1;k<i;k++){
                        if(chess[k][y]!='.'){
                            barrier=true;
                        }
                    }
                }
                else{
                    for(int k=x-1;k>i;k--){
                        if(chess[k][y]!='.'){
                            barrier=true;
                        }
                    }
                }
                //如果车和将之间没有其它棋子，牛妹胜利
                if(!barrier){
                    win=true;
                }
            }
        }

        for(int j=0;j<n;j++){
            //同一行上是否有车
            if(chess[x][j]=='C'){
                boolean barrier=false;
                if(j>y){
                    for(int k=y+1;k<j;k++){
                        if(chess[x][k]!='.'){
                            barrier=true;
                        }
                    }
                }
                else{
                    for(int k=y-1;k>j;k--){
                        if(chess[x][k]!='.'){
                            barrier=true;
                        }
                    }
                }
                if(!barrier){
                    win=true;
                }
            }
        }
        return win;
    }

    //判断牛妹是否能用炮取得胜利
    private boolean winByGun(){
        boolean win=false;
        for(int i=0;i<m;i++){
            //同一列上是否有炮
            if(chess[i][y]=='P'){
                int cnt=0;
                if(i>x){
                    for(int k=x+1;k<i;k++){
                        if(chess[k][y]!='.'){
                            cnt++;
                        }
                    }
                }
                else{
                    for(int k=x-1;k>i;k--){
                        if(chess[k][y]!='.'){
                            cnt++;
                        }
                    }
                }
                if(cnt==1){
                    win=true;
                }
            }
        }

        for(int j=0;j<n;j++){
            //同一行上是否有炮
            if(chess[x][j]=='P'){
                int cnt=0;
                if(j>y){
                    for(int k=y+1;k<j;k++){
                        if(chess[x][k]!='.'){
                            cnt++;
                        }
                    }
                }
                else{
                    for(int k=y-1;k>j;k--){
                        if(chess[x][k]!='.'){
                            cnt++;
                        }
                    }
                }
                //如果炮和将之间仅有一个棋子，牛妹胜利
                if(cnt==1){
                    win=true;
                }
            }
        }
        return win;
    }

}

3.复杂度分析

时间复杂度：寻找牛牛将的时候，最多循环 $图片说明$ 次，然后以车或炮获胜时，最多循环 $图片说明$ ，所以时间复杂度是 $图片说明$ 。
空间复杂度：需要额外大小为 $图片说明$ 的chess数组，所以空间复杂度为 $图片说明$ 。