IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		图片批量下载器
↓批量下载图片,美女图库↓ 		图片自动播放器
↓图片自动播放器↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> P5380 鸭棋 -> 正文阅读

[数据结构与算法]P5380 鸭棋

目录

原题链接

P5380

题目描述

这题真的很水，只需要用到一个算法——模拟算法
题目的大致意思如下：
有一个游戏，名字叫做鸭棋，这个游戏与象棋十分相似，但是象可以过河，是和将都可以出格，而且没有炮，原来的炮变成了鸭。棋子的走法与原来一样，鸭的话，最多可以到达8个点：
鸭棋
但是，并不是所有情况下这些点都可以去，有一个情况叫做蹩鸭腿：
鸭棋2
当你想要从深绿色的点去到浅绿色的点时，必须在当前这条路上的所有红点都没有棋子时才能实现（黑色的斜线和格子中间的线便是路线）。
棋盘的初始形态为：
棋盘
注意：棋盘的左下角才是坐标 ( 0 , 0 ) (0,0) (0,0)
另外，还有一点温馨提示：棋手下棋的顺序为：红方，蓝方，红方，蓝方……

输入格式

第一行一个非负整数 n ( n ≤ 1000 ) n(n\le 1000) n(n≤1000)，表示操作序列的长度。接下来依次描述每个操作。接下来n行，每行4个整数，表示欲将 ( y 1 , x 1 ) (y_1,x_1) (y1?,x1?)处棋子移动到 ( y 2 , x 2 ) (y_2,x_2) (y2?,x2?)处的操作。
注意：输入的坐标都为先行再列。

输出格式

输出 QQ 行，对于每个操作依次输出复现结果。每行输出一个操作的结果：

如果该操作为不合法操作，则请输出 Invalid command。
如果为合法操作，则依次回答「题目描述」中的问题 1 ～ 4 1\sim 4 1～4：

  1. 被移动的棋子用 [ [ [颜色 ] ] ] [ [ [类型 ] ] ]（注意中间包含空格）来描述，请使用它们的英文名称（见「附注」）。如，红象为 red elephant，蓝王为 blue captain。
  2. 被移出游戏的棋子的描述方式与上面类似。特别地，如果无棋子被移出游戏，则该问题的答案为 NA。
  3. 用 yes、no 分别表示形成、不形成将军局面。
  4. 用 yes、no 分别表示游戏结束、游戏不结束。
    用“ ; ”（分号）将所有问题的答案隔开。
    比如，四个问题的答案分别为：被移动的棋子是蓝车，无棋子被移出游戏，形成将军局面，游戏未结束。则该行应输出 car;NA;yes;no

附注

王（captain)
士（guard）
象（elephant）
马（horse）
车（car）
鸭（duck）
兵（soldier）

解题思路

没什么说的，就是暴力模拟，只是代码有亿点长。

代码实现

#include<bits/stdc++.h>
using namespace std;
int x_2,y_2,x_1,y_1,n,s_way[8][2]={{0,1},{1,0},{-1,0},{0,-1},{1,1},{1,-1},{-1,-1},{-1,1}}/*兵的移动方向*/,king_way[4][2]={{0,1},{1,0},{-1,0},{0,-1}}/*将的移动方向*/;
int g_way[4][2]={{1,1},{1,-1},{-1,1},{-1,-1}}/*士的移动方向*/,e_way[4][2]={{2,2},{2,-2},{-2,2},{-2,-2}};/*象的移动方向*/
int h_way[8][2][2]={{{1,-2},{0,-1}},{{2,-1},{1,0}},{{2,1},{1,0}},{{1,2},{0,1}},{{-1,2},{0,1}},{{-2,1},{-1,0}},{{-2,-1},{-1,0}},{{-1,-2},{0,-1}}}/*马的移动方向{{去终点的坐标对于当前位置的变化},{蹩马腿，对于当前位置的坐标变化}}*/;
int d_way[8][2][2][2]=
{{{{-3,2},{0,0}},{{-1,0},{-2,1}}},
{{{-2,3},{0,0}},{{0,1},{-1,2}}},
{{{2,3},{0,0}},{{0,1},{1,2}}},
{{{3,2},{0,0}},{{1,0},{2,1}}},
{{{3,-2},{0,0}},{{1,0},{2,-1}}},
{{{2,-3},{0,0}},{{0,-1},{1,-2}}},
{{{-2,-3},{0,0}},{{0,-1},{-1,-2}}},
{{{-3,-2},{0,0}},{{-1,0},{-2,-1}}}}/*鸭的移动方向{{去终点的坐标对于当前位置的变化},{蹩鸭腿，对于当前位置的坐标变化}}*/;
int color=1; 
string ans_chess[200],ans_color[10];
bool game=true,f1,f2,f3,f4;
char a[10][9]=
{
{'c','h','e','g','k','g','e','h','c'},
{' ',' ',' ',' ',' ',' ',' ',' ',' '},
{'d',' ',' ',' ',' ',' ',' ',' ','d'},
{'s',' ','s',' ','s',' ','s',' ','s'},
{' ',' ',' ',' ',' ',' ',' ',' ',' '},
{' ',' ',' ',' ',' ',' ',' ',' ',' '},
{'s',' ','s',' ','s',' ','s',' ','s'},
{'d',' ',' ',' ',' ',' ',' ',' ','d'},
{' ',' ',' ',' ',' ',' ',' ',' ',' '},
{'c','h','e','g','k','g','e','h','c'}
};//初始棋盘
int c[10][9]=
{
{2,2,2,2,2,2,2,2,2},
{0,0,0,0,0,0,0,0,0},
{2,0,0,0,0,0,0,0,2},
{2,0,2,0,2,0,2,0,2},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{1,0,1,0,1,0,1,0,1},
{1,0,0,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0,0},
{1,1,1,1,1,1,1,1,1}
};//颜色，1为蓝色，2为红色，倒过来方便处理
bool chk(int x,int y)//出界判断
{
	return x>=0&&x<10&&y>=0&&y<9;
}
void setup()//字母对应的棋子和数字对应的颜色
{
	ans_chess['k']="captain";
	ans_chess['g']="guard";
	ans_chess['e']="elephant";
	ans_chess['h']="horse";
	ans_chess['c']="car";
	ans_chess['d']="duck";
	ans_chess['s']="soldier";
	ans_color[1]="blue";
	ans_color[2]="red";
	return; 
}
bool move_king(int x,int y,int ex,int ey,int cl)//判断王的移动
{
	for(int i=0;i<4;i++)
		if(chk(x+king_way[i][0],y+king_way[i][1]))//检查是否出界
			if(x+king_way[i][0]==ex&&y+king_way[i][1]==ey)//判断是否到达终点
				return true;
	return false;
}
bool move_soldier(int x,int y,int ex,int ey,int cl)//判断兵的移动
{
	for(int i=0;i<8;i++)
		if(chk(x+s_way[i][0],y+s_way[i][1]))//检查是否出界
			if(x+s_way[i][0]==ex&&y+s_way[i][1]==ey)//判断是否到达终点
				return true;
	return false;
}
bool move_guard(int x,int y,int ex,int ey,int cl)//判断士的移动
{
	for(int i=0;i<4;i++)
		if(chk(x+g_way[i][0],y+g_way[i][1]))//检查是否出界
			if(x+g_way[i][0]==ex&&y+g_way[i][1]==ey)//判断是否到达终点
				return true;
	return false;
}
bool move_elephant(int x,int y,int ex,int ey,int cl)//判断象的移动
{
	for(int i=0;i<4;i++)
		if(chk(x+e_way[i][0],y+e_way[i][1])&&a[x+e_way[i][0]/2][y+e_way[i][1]/2]==' ')//检查是否出界和是否蹩象腿
			if(x+e_way[i][0]==ex&&y+e_way[i][1]==ey)//判断是否到达终点
				return true;
	return false;
}
bool move_horse(int x,int y,int ex,int ey,int cl)//判断马的移动
{
	for(int i=0;i<8;i++)
		if(chk(x+h_way[i][0][0],y+h_way[i][0][1])&&a[x+h_way[i][1][0]][y+h_way[i][1][1]]==' ')//检查是否出界和是否蹩马腿
			if(x+h_way[i][0][0]==ex&&y+h_way[i][0][1]==ey)//判断是否到达终点
				return true;
	return false;
}
bool move_car(int x,int y,int ex,int ey,int cl)//判断车的移动
{
	if(x!=ex&&y!=ey)
		return false;
	int x_change,y_change;//x和y的变化方向
	if(x!=ex)
		if(x<ex){
			x_change=1;
			y_change=0;
		}
		else{
			x_change=-1;
			y_change=0;
		}
	else{
		if(y<ey){
			x_change=0;
			y_change=1;
		}
		else{
			x_change=0;
			y_change=-1;
		}
	}
	while(x!=ex||y!=ey){//判断是否到达终点
		x+=x_change;
		y+=y_change;
		if(!chk(x,y))//检查是否出界
			return false;
		if(a[x][y]!=' '&&(x!=ex||y!=ey))
			return false;
	}
	return true;
}
bool move_duck(int x,int y,int ex,int ey,int cl)//判断鸭的移动
{
	for(int i=0;i<8;i++)
		if(chk(x+d_way[i][0][0][0],y+d_way[i][0][0][1])&&a[x+d_way[i][1][0][0]][y+d_way[i][1][0][1]]==' '&&a[x+d_way[i][1][1][0]][y+d_way[i][1][1][1]]==' ')//检查是否出界和是否蹩鸭腿
			if(x+d_way[i][0][0][0]==ex&&y+d_way[i][0][0][1]==ey)//判断是否到达终点
				return true;
	return false;
}
bool c_m()//判断是否将军
{
	int k_p[10][10];
	for(int i=0;i<10;i++)//获取将军的位置
		for(int j=0;j<9;j++)
			if(a[i][j]=='k'){
				k_p[c[i][j]][0]=i;
				k_p[c[i][j]][1]=j;
			}
	for(int i=0;i<10;i++){//将棋盘上每一个棋都判断一次是否可以一步吃掉将军
		for(int j=0;j<9;j++){
			if(c[i][j]==1){
				switch(a[i][j]){
					case 'k':{
						if(move_king(i,j,k_p[2][0],k_p[2][1],1))
							return true;
						break;
					}
					case 'c':{
						if(move_car(i,j,k_p[2][0],k_p[2][1],1))
							return true;
						break;
					}
					case 'e':{
						if(move_elephant(i,j,k_p[2][0],k_p[2][1],1))
							return true;
						break;
					}
					case 'g':{
						if(move_guard(i,j,k_p[2][0],k_p[2][1],1))
							return true;
						break;
					}
					case 'h':{
						if(move_horse(i,j,k_p[2][0],k_p[2][1],1))
							return true;
						break;
					}
					case 's':{
						if(move_soldier(i,j,k_p[2][0],k_p[2][1],1))
							return true;
						break;
					}
					case 'd':{
						if(move_duck(i,j,k_p[2][0],k_p[2][1],1))
							return true;
						break;
					}
				}
			}
			else if(c[i][j]==2){
				switch(a[i][j]){
					case 'k':{
						if(move_king(i,j,k_p[1][0],k_p[1][1],2))
							return true;
						break;
					}
					case 'c':{
						if(move_car(i,j,k_p[1][0],k_p[1][1],2))
							return true;
						break;
					}
					case 'e':{
						if(move_elephant(i,j,k_p[1][0],k_p[1][1],2))
							return true;
						break;
					}
					case 'g':{
						if(move_guard(i,j,k_p[1][0],k_p[1][1],2))
							return true;
						break;
					}
					case 'h':{
						if(move_horse(i,j,k_p[1][0],k_p[1][1],2))
							return true;
						break;
					}
					case 's':{
						if(move_soldier(i,j,k_p[1][0],k_p[1][1],2))
							return true;
						break;
					}
					case 'd':{
						if(move_duck(i,j,k_p[1][0],k_p[1][1],2))
							return true;
						break;
					}
				}
			}
		}
	}
	return false;
}
void back_stap()//移动棋子
{
	c[x_2][y_2]=c[x_1][y_1];
	c[x_1][y_1]=0;
	a[x_2][y_2]=a[x_1][y_1];
	a[x_1][y_1]=' ';
	return;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie();
	cin>>n;
	setup();
	for(int i=1;i<=n;i++){
		cin>>x_1>>y_1>>x_2>>y_2;
		if(!chk(x_1,y_1)||!chk(x_2,y_2)){
			cout<<"Invalid command"<<endl;
			continue;
		}
		if(!game){
			cout<<"Invalid command"<<endl;
			continue;
		}
		if(a[x_1][y_1]==' '||x_1==x_2&&y_1==y_2){
			cout<<"Invalid command"<<endl;
			continue;
		}
		if(c[x_2][y_2]==c[x_1][y_1]){
			cout<<"Invalid command"<<endl;
			continue;
		}
		if(c[x_1][y_1]!=color+1){
			cout<<"Invalid command"<<endl;
			continue;
		}
		f1=false;
		switch(a[x_1][y_1]){
			case 'k':{
				if(move_king(x_1,y_1,x_2,y_2,c[x_1][y_1])){
					cout<<ans_color[c[x_1][y_1]]<<" "<<ans_chess[a[x_1][y_1]]<<";";//移动的棋子
					if(c[x_2][y_2]!=c[x_1][y_1]&&c[x_2][y_2]!=0){
						cout<<ans_color[c[x_2][y_2]]<<" "<<ans_chess[a[x_2][y_2]]<<";";//被吃的棋子
						if(a[x_2][y_2]=='k')//游戏结束
							game=false;
					}
					else{
						cout<<"NA;";//没有棋被吃
					}
					back_stap();//将棋子移动
					f1=true;
				}
				break;
			}
			case 's':{
				if(move_soldier(x_1,y_1,x_2,y_2,c[x_1][y_1])){
					cout<<ans_color[c[x_1][y_1]]<<" "<<ans_chess[a[x_1][y_1]]<<";";//移动的棋子
					if(c[x_2][y_2]!=c[x_1][y_1]&&c[x_2][y_2]!=0){
						cout<<ans_color[c[x_2][y_2]]<<" "<<ans_chess[a[x_2][y_2]]<<";";//被吃的棋子
						if(a[x_2][y_2]=='k')//游戏结束
							game=false;
					}
					else{
						cout<<"NA;";//没有棋被吃
					}
					back_stap();//将棋子移动
					f1=true;
				}
				break;
			}
			case 'g':{
				if(move_guard(x_1,y_1,x_2,y_2,c[x_1][y_1])){
					cout<<ans_color[c[x_1][y_1]]<<" "<<ans_chess[a[x_1][y_1]]<<";";//移动的棋子
					if(c[x_2][y_2]!=c[x_1][y_1]&&c[x_2][y_2]!=0){
						cout<<ans_color[c[x_2][y_2]]<<" "<<ans_chess[a[x_2][y_2]]<<";";//被吃的棋子
						if(a[x_2][y_2]=='k')//游戏结束
							game=false;
					}
					else{
						cout<<"NA;";//没有棋被吃
					}
					back_stap();//将棋子移动
					f1=true;
				}
				break;
			}
			case 'e':{
				if(move_elephant(x_1,y_1,x_2,y_2,c[x_1][y_1])){
					cout<<ans_color[c[x_1][y_1]]<<" "<<ans_chess[a[x_1][y_1]]<<";";//移动的棋子
					if(c[x_2][y_2]!=c[x_1][y_1]&&c[x_2][y_2]!=0){
						cout<<ans_color[c[x_2][y_2]]<<" "<<ans_chess[a[x_2][y_2]]<<";";//被吃的棋子
						if(a[x_2][y_2]=='k')//游戏结束
							game=false;
					}
					else{
						cout<<"NA;";//没有棋被吃
					}
					back_stap();//将棋子移动
					f1=true;
				}
				break;
			}
			case 'd':{
				if(move_duck(x_1,y_1,x_2,y_2,c[x_1][y_1])){
					cout<<ans_color[c[x_1][y_1]]<<" "<<ans_chess[a[x_1][y_1]]<<";";//移动的棋子
					if(c[x_2][y_2]!=c[x_1][y_1]&&c[x_2][y_2]!=0){
						cout<<ans_color[c[x_2][y_2]]<<" "<<ans_chess[a[x_2][y_2]]<<";";//被吃的棋子
						if(a[x_2][y_2]=='k')//游戏结束
							game=false;
					}
					else{
						cout<<"NA;";//没有棋被吃
					}
					back_stap();//将棋子移动
					f1=true;
				}
				break;
			}
			case 'c':{
				if(move_car(x_1,y_1,x_2,y_2,c[x_1][y_1])){
					cout<<ans_color[c[x_1][y_1]]<<" "<<ans_chess[a[x_1][y_1]]<<";";//移动的棋子
					if(c[x_2][y_2]!=c[x_1][y_1]&&c[x_2][y_2]!=0){
						cout<<ans_color[c[x_2][y_2]]<<" "<<ans_chess[a[x_2][y_2]]<<";";//被吃的棋子
						if(a[x_2][y_2]=='k')//游戏结束
							game=false;
					}
					else{
						cout<<"NA;";//没有棋被吃
					}
					back_stap();//将棋子移动
					f1=true;
				}
				break;
			}
			case 'h':{
				if(move_horse(x_1,y_1,x_2,y_2,c[x_1][y_1])){
					cout<<ans_color[c[x_1][y_1]]<<" "<<ans_chess[a[x_1][y_1]]<<";";//移动的棋子
					if(c[x_2][y_2]!=c[x_1][y_1]&&c[x_2][y_2]!=0){
						cout<<ans_color[c[x_2][y_2]]<<" "<<ans_chess[a[x_2][y_2]]<<";";//被吃的棋子
						if(a[x_2][y_2]=='k')//游戏结束
							game=false;
					}
					else{
						cout<<"NA;";//没有棋被吃
					}
					back_stap();//将棋子移动
					f1=true;
				}
				break;
			}
		}
		if(!f1){
			cout<<"Invalid command"<<endl;//走不了
			continue;
		}
		if(c_m())//是否将军
			cout<<"yes;";
		else
			cout<<"no;";
		if(game)//游戏是否结束
			cout<<"no"<<endl;
		else
			cout<<"yes"<<endl;
		color=(color+1)%2;//当前棋手的编号
	}
}

样例

输入

18
0 0 7 0
9 0 8 0
0 1 1 3
0 2 2 0
0 3 1 2
0 4 0 3
9 4 8 4
3 2 2 3
7 0 4 2
7 0 5 3
9 2 7 4
2 0 4 3
9 1 8 3
4 3 6 6
7 4 9 2
8 4 9 4
6 6 9 4
9 8 8 8

输出

Invalid command
Invalid command
Invalid command
Invalid command
red guard;NA;no;no
Invalid command
blue captain;NA;no;no
red soldier;NA;no;no
Invalid command
Invalid command
blue elephant;NA;no;no
red duck;NA;no;no
blue horse;NA;no;no
red duck;blue soldier;no;no
Invalid command
blue captain;NA;yes;no
red duck;blue captain;no;yes
Invalid command
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用：海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题＜有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-10-02 15:06:48  更:2021-10-02 15:09:42 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年5日历 -2024/5/17 11:49:58-

图片自动播放器
↓图片自动播放器↓ 		TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓ 		图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码