题解 | #下象棋#
下象棋
http://www.nowcoder.com/practice/2b0f51e8b1594d7091576dab05e00693
题目描述
棋盘中包含四种棋子:炮P、将J、车C、兵B
牛妹棋子用大写字母表示,牛牛棋子用小写字母表示
问一回合内牛妹能否战胜牛牛
方法一 模拟
解题思路
棋子只能吃掉与自己同一行或同一列的棋子，所以可以只考虑与牛牛的将同一行或同一列的棋子。
对于牛妹的兵和将，需要位于牛牛的将上下左右四个相邻的位置；对于牛妹的车，与牛牛的将之间不能有其棋子；对于牛妹的炮，与牛牛的将之间有且只有一个棋子。
对于兵和将，要想获胜，需要：
对于车，要想获胜，需要：
对于炮，要想获胜，需要：
按照上述规则，检查与j同一行和同一列的棋子即可。
代码示例
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param chessboard string字符串vector
* @return string字符串
*/
string playchess(vector<string>& chessboard) {
// n，m表示chessboard的大小
int n = chessboard.size(), m = chessboard[0].size();
vector<vector<int>>dir = { {0,-1},{0,1},{-1,0},{1,0} };
// 遍历棋盘，找到j所在的位置
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
// 找到了j的位置
if (chessboard[i][j] == 'j')
{
// 用变量k来遍历j的四个方向
for (int k = 0; k < 4; k++)
// nx，ny为与牛牛同一行或同一列的坐标位置
// cnt初始为0，用来记录棋盘中[nx,ny]与[i,j]之间棋子的个数（用于车和炮的判断）
// l用来记录与牛牛的将的距离（用于兵和将的判断）
for (int cnt = 0, nx = i + dir[k][0], ny = j + dir[k][1], l = 2;
nx >= 0 && nx < n && ny >= 0 && ny < m;
nx = i + dir[k][0] * l, ny = j + dir[k][1] * l, l++)
{
// 如果遍历到的位置是牛妹的棋子，根据条件判断是否能取胜
// 兵和将：与牛妹的将必须相邻，即l==2
// 炮：与牛妹的将之间有一个棋子，即cnt==1
// 车：与牛妹的将之间没有棋子，即cnt==0
if (((chessboard[nx][ny] == 'B' || chessboard[nx][ny] == 'J') && l == 2)
|| (chessboard[nx][ny] == 'P' && cnt == 1) || (chessboard[nx][ny] == 'C' && !cnt))
return "Happy";
cnt += chessboard[nx][ny] != '.';
// 与牛牛的将之间至少两个棋子，不可能获胜
if (cnt > 1)
break;
}
break;
}
return "Sad";
}
}; 复杂度分析
- 时间复杂度：需要先遍历一遍棋盘，找到牛牛将的位置，
。找到牛牛将的位置之后，需要遍历一行和一列，时间复杂度为
。所以总的时间复杂度为
- 空间复杂度：使用了常数个变量，空间复杂度为
方法二 分类讨论
解题思路
方法一是以牛牛的将为中心进行模拟，还可以以牛妹的棋子为中心进行模拟。
具体来说，我们只需要对牛妹的每个棋子判断其能否吃掉牛牛的将，如果都吃不掉，那么牛妹便此回合不能获胜，否则牛妹此回合可以获胜。
具体规则与方法一一样：
对于牛妹的兵和将，需要位于牛牛的将上下左右四个相邻的位置；对于牛妹的车，与牛牛的将之间不能有其棋子；对于牛妹的炮，与牛牛的将之间有且只有一个棋子。
可以考虑使用两个pair存储棋子种类和棋子的x、y坐标，在对行和列遍历时，可以根据这两个数组快速进行判断。以对行遍历为例，如果棋子是P，那么需要查询与P相隔一个棋子的棋子是否为j；如果棋子是J/B，那么需要查询该棋子邻居是否为j，并且距离为1；如果棋子为C，那么仅需要查询该棋子邻居是否为j。例如，对于下述棋盘，
棋子种类及其x、y坐标为：
代码示例
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param chessboard string字符串vector
* @return string字符串
*/
string playchess(vector<string>& chessboard) {
// n，m为chessboard的大小
int n=chessboard.size(), m=chessboard[0].size();
// 存储棋子种类和它的x，y坐标
vector<pair<char,int>> x[n+1],y[m+1];
// 存储棋子种类和它的x坐标
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});
// 存储棋子种类和它的y坐标
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});
// fg==0：不能获胜；fg==1，可以获胜
int fg=0;
// 遍历每一行
for(int i=1;i<=n;i++) {
// 取出所有棋子及其x坐标
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') {
// 与牛牛的将相邻，距离为1
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') {
// 与牛牛的将相邻，距离为1
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";
}
}; 复杂度分析
- 时间复杂度：需要遍历一遍棋盘得到所有棋子的x，y坐标；然后需要对每一行、每一列的棋子进行便利，时间复杂度为
- 空间复杂度：需要大小为
