算法思想一：模拟搜索
解题思路：
逆向思维思考，因为所有棋子都只能上下左右移动，所以为了判断牛牛的将能否被吃下，只需要判断牛牛的那一行与列的棋子情况即可。
1、首先找到牛牛的将在什么位置。
2、以牛牛将的位置为起点，沿着四个方向进行搜索，当与起点位置相邻，
1、并且当前位置是牛妹的将或兵时，说明牛妹可以赢，直接返回"Happy";
2、当与起点位置之间的棋子数为0个，并且当前位置是牛妹的车时，说明牛妹可以赢，直接返回"Happy"；
3、当与起点位置之间的棋子数只有一个，并且当前位置是牛妹的炮时，说明牛妹可以赢，直接返回"Happy"。
3、最后，如果没有找到赢得情况，返回"Sad"。
图解：
代码展示：
Python版本
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param chessboard string字符串一维数组
# @return string字符串
#
class Solution:
def playchess(self , chessboard ):
# write code here
h = len(chessboard)
l = len(chessboard[0])
#用一个数组定义四个方向
dir=[[0,-1],[0,1],[-1,0],[1,0]]
for i in range(0,h):
for j in range(0,l):
# 找到牛牛的 将 的位置
if chessboard[i][j]=='j':
#遍历四个方向的棋子
count = 1
for k in range(0,4):
inval = 0 #记录将与车之间间隔的其他棋子
n,c = i,j#定位到当前行和列
count = 1 #控制while循环
while count > 0:
n = n + dir[k][0]#行数
c = c + dir[k][1]#列数
# 边界范围
if n>=0 and c>=0 and n<h and c < l:
# 如果有 兵 或者 将、
if (chessboard[n][c]=='B' or chessboard[n][c]=='J') and count ==1:
return "Happy"
# 炮的位置，且中间隔得有棋子
if chessboard[n][c]=='P' and inval>0:
return "Happy"
# 存在 车 且中间没有棋子
if chessboard[n][c] == 'C' and inval == 0:
return "Happy"
if chessboard[n][c]!='.':
inval =inval+1
count = count+1
else:
count = 0
if k == 3 and count == 0:
return "Sad"#全部遍历完成后没有符合条件的为输 复杂度分析
时间复杂度：n m表示棋盘的大小，以扫描牛牛的将所在的位置，再对那一行一列进行判断。时间复杂度
空间复杂度：仅使用常数级变量空间
算法思想二：分场景分析
解题思路：
只需要分别判断牛妹的炮，将，兵，车能否攻下牛牛的将，只要满足其中之一，就返回"Happy"，否则返回"Sad"。
具体来说：
1、对于兵和将，只可能在牛牛的将的上下左右四个相邻的方向上才能取胜；
2、对于车来说，只可能在上下左右四个方向上并且与牛牛的将之间没有其他棋子时才能取胜；
3、对于炮来说，只可能在上下左右四个方向上并且与牛牛的将之间有且仅有一个其他棋子时才能取胜。
对地图分别按照轴与轴进行了离散化，对于每一个与存储了他这一行/一列的棋子信息，然后只需要分别遍历离散化后轴与轴数组，看看每一类棋子能否攻下牛牛的将即可
代码展示：
C++版本
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>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";
}
}; JAVA版本
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) {
// write code here
//计算棋盘的长和宽
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;
}
} 复杂度分析
时间复杂度：n m表示棋盘的大小，从行 列同时遍历搜索时间
空间复杂度：额外数组占用空间
京公网安备 11010502036488号