题目描述
牛妹在和牛牛下牛客象棋。现在轮到牛妹了，牛妹想知道她在这一回合能否战胜牛牛。
棋盘chessboard上只可能包含：炮，将，车，兵
牛客象棋的规则解释：
炮：炮在不吃子的时候，走动与车完全相同，但炮在吃棋子时，必须跳过一个棋子，我方的和敌方的都可以
兵：可以上下左右移动，每次只能移动一格
车：上下左右均可走，只要无棋子阻拦，步数不受限制。
将：可以上下左右移动，每次只能移动一格
接下来给出一个棋盘，牛妹的棋子用大写字母表示，牛牛的棋子用小写字母表示。
将用J,jJ,j表示，炮用P,pP,p表示，车用C,cC,c表示，兵用B,bB,b表示，没有棋子的格子用..表示
保证棋盘上一定同时包含JJ与jj各一个。
牛妹能胜利则返回"Happy"，否则返回"Sad"
方法一：暴力解法
求解思路
对于本题牛妹能否取得胜利，我们可以采用枚举的方法，将牛妹获胜的情况一一列举出来。我们首先找到牛牛的“将”在什么位置，然后我们分四种情况进行讨论，看牛牛是否能用兵，将，车，炮中的某一颗棋子赢得胜利。只要满足其中的一种，就返回“happy”，否则的话返回“sad”。
解题代码
import java.util.*;
public class Solution {
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 count=0;
if(i>x)
{
for(int k=x+1;k<i;k++)
{
if(chess[k][y]!='.')
{
count++;
}
}
}
else
{
for(int k=x-1;k>i;k--)
{
if(chess[k][y]!='.')
{
count++;
}
}
}
if(count==1)
{
win=true;
}
}
}
for(int j=0;j<n;j++)
{ //同一行上是否有炮
if(chess[x][j]=='P')
{
int count=0;
if(j>y)
{
for(int k=y+1;k<j;k++)
{
if(chess[x][k]!='.')
{
count++;
}
}
}
else{
for(int k=y-1;k>j;k--)
{
if(chess[x][k]!='.')
{
count++;
}
}
}
//如果炮和将之间仅有一个棋子，牛妹胜利
if(count==1)
{
win=true;
}
}
}
return win;
}
}复杂度分析
时间复杂度：两层循环，因此时间复杂度为(
)
空间复杂度：引入chess[n][n]，使用额外的内存地址空间，因此空间复杂度为(
)
方法二：模拟搜索的思想求解
求解思路
基于方法一，我们对解法进行优化。我们首先找到牛牛的“将”在什么位置，然后以牛牛的将为起点，沿着四个方向进行搜索，当与起点位置相邻，并且当前位置是牛妹的将或者兵时，说明牛妹可以赢，此时返回“happy”。当与起点位置之间的棋子数为0个，并且当前位置是牛妹的“车”时，说明牛妹可以赢，直接返回“happy”，同样当前位置是牛妹的“炮”时，也返回“happy”。最后如果没有找到赢的情况，则返回“sad”。
解题代码
import java.util.*;
public class Solution {
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 count=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')&&count==1)
||((chessboard[nx].charAt(ny)=='C')&&count==0))
{
return "Happy";
}
neighbor=false;
if(chessboard[nx].charAt(ny)!='.')
{
count++;
}
//如果障碍棋子超过2，直接终止搜索
if(count>1)
{
break;
}
//下一个位置
nx+=directions[k][0]; // 更新位置
ny+=directions[k][1]; // 更新位置
}
}
return "Sad";
}
}复杂度分析
时间复杂度：两层循环，因此时间复杂度为(
)
空间复杂度：引入常数级别的数组，因此空间复杂度为
京公网安备 11010502036488号