题目链接:uva 278 - Chess
题目大意:给出一个n*m的棋盘,并且给出棋子的种类,问说在这个大小的棋盘上最多能放几个给定的棋子,棋子之间不能互相攻击。
解题思路:总共有4种棋子,那么就分类讨论。
马(骑士):
n或m为1的时候,肯定可以摆满,因为肯定不能互相攻击
n或者m为2时,这样放是最优的。
其他情况的或就是间隔放最优。
车:因为车的攻击方式是直线,所以每放一个车就会攻击到一列一行,所以答案就是n和m中最小的那个。
国王:国王的攻击范围是周围8个格子,所以放法就像考试隔排隔位一样。
皇后:皇后不仅可以攻击直线,还可以攻击斜线,所以放的个数肯定不能比车放的要多,那么就考虑min(n,m)能不能放下,这里n和m恰好大于等于4,学习8皇后问题的时候有一个知识点,就是n*n的矩阵,n ≥4的话是有解的。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int t[4] = {0, 2, 4, 0};
int m, n;
char ch[20];
int knight() {
int p = max(n, m);
int q = min(n, m);
if (q == 1) {
return p;
} else if (q == 2) {
int s = p / 4;
int d = p % 4;
return s * 4 + t[d];
} else
return (n * m + 1) / 2;
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
scanf("%s%d%d", ch, &m, &n);
if (ch[0] == 'r')
printf("%d\n", min(m, n));
else if (ch[0] == 'k')
printf("%d\n", knight());
else if (ch[0] == 'Q')
printf("%d\n", min(m, n));
else if (ch[0] == 'K')
printf("%d\n", (n+1)/2 * ((m+1)/2));
}
return 0;
}
分享到:
相关推荐
北大POJ1321-Chess Problem POJ1321-Chess Problem
command-line-chess, 在终端上,一个 python 程序,用来玩国际象棋 command-line-chess在终端上玩国际象棋的python 程序。##Installation需要 python 3,运行以下命令安装:pip3 install cl-chess##Usage安装后
(*)为e-chess sudo docker pull coderon98/e-chess:beta : sudo docker pull coderon98/e-chess:beta (**)构建docker容器并运行它: sudo docker run -it --name e-chess -e DISPLAY=$DISPLAY -v /tmp/.X11-...
python库。 资源全名:python-chess-0.8.0.tar.gz
IOS应用源码——vonProteus-iPhone-OpenGL-Chess-8636ccc.rar
iOS游戏应用源代码——vonProteus-iPhone-OpenGL-Chess-8636ccc.zip
中国象棋-chess.m 我从网上下载的中国象棋程序,感觉不够美观,改进了下。
开源项目-notnil-chess.zip,围棋套餐
香农-《设计计算机国际象棋程序 》 英文名: Shannon---Programming-a-computer-for-playing-chess
c-chess-cli c-chess-cli是用于用C编写的UCI国际象棋引擎的命令行界面。没有,它仅使用C标准库和POSIX。它最初是在Linux上开发的,应该可以在所有POSIX操作系统上使用,包括MacOS和Android。不支持Windows。如何编译...
前端项目-chess.js,一个用于生成/验证国际象棋移动、放置/移动棋子和检查/检查/绘制检测的javascript国际象棋库。
JS-CHESS-ENGINE 简单JavaScript国际象棋引擎,没有用NodeJs编写的依赖项。 它既可以在服务器上也可以在客户端(网络浏览器)上使用,并且不需要持久性存储-方便用于AWS Lambda等无服务器解决方案。 该引擎还包括可...
国际象棋程序-chess.rar 完全功能,有历史记录,反应很快,可悔棋。 附件: 巨多:解压后运行主文件,chess.m即可。 里边还有作者写的一个pdf的象棋教程,功能未曾试完。 附件: chess.rar
3D-04-Low-Poly-Chess-Set-Original.zip,低保利国际象棋(CS_CBC)http://gdev.tv/cbcgithub,3D建模使用专门的软件来创建物理对象的数字模型。它是3D计算机图形的一个方面,用于视频游戏,3D打印和VR,以及其他应用...
python库。 资源全名:django-chess-0.2.1.tar.gz
中国象棋-chess1.m 我从matlab技术论坛下了个中国象棋程序,对其进行了小的改进,但是属于自己个自己对弈的,在此分享给大家,有志之士可以进一步改进。
资源来自pypi官网。 资源全名:python-chess-0.0.3.tar.gz
swift-chess:一个采用 Swift 2.0开发的简单棋类游戏
https://github.com/japtar10101/Chess-Clock-App The MIT License Copyright (c) 2011 Taro Omiya Permission is hereby granted, free of charge, to any person obtaining a copy of this soft