题解 | #下象棋#
下象棋
http://www.nowcoder.com/practice/2b0f51e8b1594d7091576dab05e00693
题意整理
- 只要牛妹的炮，将，车，兵的任意一个能吃到牛牛的将，则牛妹获胜。
- 将、兵只有在相邻的时候才能吃。
- 炮、车在同行和同列都可以吃，炮需要隔一个棋子，车不能有棋子挡在中间。
方法一（模拟搜索）
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.复杂度分析
- 时间复杂度：寻找牛牛将的时候，最多循环
，所以时间复杂度是
。
- 空间复杂度：需要额外大小为
xqxls的题解 文章被收录于专栏
牛客题解
