5088: Nine Knights
In the game of chess, knights are unique due to their “L-shaped” movement. A knight can move, as shown in figure A.1, by either moving two squares sideways and one square up or down, or moving one square sideways and two squares either up or down.
figure A.1: The highlight e d squares show all possible moves for a knight. In the Nine Knights puzzle, exactly nine knights must be positioned on a 5-by-5 board so that no knight can attack another knight with a single move. The configuration shown in figure A.2 is an invalid solution because two of the knights can attack each other, where the configuration shown in figure A.3 is a valid solution.
figure A.2: Invalid game configuration figure A.3: Valid game configuration Given the description of a game configuration, your job is to determine whether or not it represents a valid solution to the Nine Knights puzzle.
输入
The input will consist of 5 lines, each having 5 characters. All characters will be either ’k’, indicating the placement of a knight, or ’.’, indicating an empty space on the board.输出
Display the word valid if the given chess board is a valid solution to the Nine Knights puzzle. Otherwise,display the word invalid. （★如果给定的棋盘是九骑士谜题的有效解决方案，则显示 valid，否则，显示 invalid）样例输入
...k. ...k.
k.k..
.k.k.
k.k.k 样例输出
invalid 题意：机器人只能走“L”，通过移动两个正方形侧面和一个正方形向上或向下，或者移动一个正方形侧面和两个正方形向上或向下，要求机器人无论怎么走都不会有重合的情况出现。
AC代码：
#include
#include
#include
#include
using namespace std;
char maze[6][6]= {'\0'};
int ter[8][6]=
{
0,1,0,2,1,2
,0,1,0,2,-1,2
,1,0,2,0,2,1
,1,0,2,0,2,-1
,0,-1,0,-2,1,-2
,0,-1,0,-2,-1,-2
,-1,0,-2,0,-2,1
,-1,0,-2,0,-2,-1
}; //机器人的8种可能移动路线
typedef struct nodee
{
int x,y;
} node; //把机器人坐标放到结构体中
int main()
{
int i,j,xx,yy,flag,countt;
queue
node now;
for(i=0; i<5; i++)
{
scanf("%s",maze[i]);
getchar();
}
countt=0;
for(i=0; i<5; i++)
{
for(j=0; j<5; j++)
{
if(maze[i][j]=='k') //如果该位置有机器人，则标记横纵坐标
{
now.x=i;
now.y=j;
q.push(now); //把标记的坐标放入队列
countt++; //标记机器人数量，判断是否为9个机器人
}
}
}
if(countt!=9)
{
printf("invalid\n");
return 0;
}
while(!q.empty())
{
now=q.front(); //此部分 队列惯用模板
q.pop();
for(i=0; i<8; i++)
{
flag=0;
for(j=0; j<4; j+=2)
{
xx=now.x+ter[i][j];
yy=now.y+ter[i][j+1];
if(xx>=0&&xx<5&&yy>=0&&yy<5&&maze[xx][yy]=='k') //保证机器人移动不越界的情况下，判断 ★移动的路上 是否已经有机器人
{
flag=1;
break;
}
}
//如果没有
xx=now.x+ter[i][4];yy=now.y+ter[i][5];
if(xx>=0&&xx<5&&yy>=0&&yy<5&&flag==0&&maze[xx][yy]=='k') //判断到达的地方是否有机器人
{
printf("invalid\n");
return 0;
}
}
}
printf("valid\n");
return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！