在3个动作中，骑士可以去哪里？ [英] In 3 moves, where can the knight go?
问题描述
这是编程比赛的一个过去的问题。
在棋盘上（8个方格，8个方格），有一个骑士坐着
$ b1上的b $ b（底行左侧2）。如果你还不知道的话，可以找出你自己如何移动骑士的话。
骑士有3个动作和程序员必须产生骑士在3次移动中所有可能位置的输出
（其中没有
这些最终位置的
也可以在2次移动中实现，例如移动2
向上1，最后1对2向下），形式如下：
OOOOOOOO
OOOOOOOO
OOOOOOOO
OOOOOOOO
OOOOOOOO
OOOOOOOO
OOOOOOOO
OOOOOOOO
^
我们用一顶帽子象征着骑士的位置，在上图中，
那就是骑士的位置总是开始。
现在我知道骑士最多可以移动8种方式。
如果我调用topleft（）骑士移动2向上1，upleft（）其中
骑士向左移动1向上，dow nleft（）骑士向下移动1
2左边和btmleft 2向下1左（直观地计算出
对应的四个）有8个函数代表骑士'' s $
可能的动作。
现在我不会使用字母和数字来代替
棋盘的坐标但是而是x和y，其中1,1是左下角
棋盘的
。所以我定义了一个名为co的结构
struct co {
int x，y;
};
每个''运动''函数返回一个struct co例如：
struct co topleft（int x，int y）
{
struct co temp;
if（（x-1）> = 1&&（y + 2）< = 8）{
temp.x = x;
temp.y = y;
返回临时数;
}其他{
temp.x = 0;
temp.y = 0;
返回临时数;
}
}
在main函数中，我打算创建一个临时struct co和一个名为pos的带有40个元素的结构数组，这是可能有点
很多。
所以：
struct co temp;
struct co pos [40];
temp.x = 2;
temp.y = 1; / *每个骑士开始的地方* /
temp = topleft（temp.x，temp.y）;
if（（temp.x！= 0）&& ;（temp.y！= 0））{
temp = topleft（temp.x，temp.y）;
if（（temp.x！= 0） &&（temp.y！= 0））
temp = topleft（temp.x，temp.y）;
if（（temp.x！= 0）&&（temp.y！= 0））
pos [0] = temp;
}
temp.x = 2;
temp.y = 1;
/ *等* /
所以它继续： topleft，topleft，topleft
topleft，topleft，topright
topleft，topleft，upleft
但我写的可能超过1000只为这个程序的代码行！
竞赛只允许，只允许2小时完成你的b $ b可以做什么，并通过电子邮件提交你的源代码和可执行文件到哪里
他们收集它！
我该如何更好地完成这个程序？我有它的要点吗？任何一个？
Bert
This is a past question from a programming competition.
On a chess board (8 squares by 8 squares), there''s is a knight sitting
on b1 (2 from the left of the bottom row). To cut the crap, find out
how a knight moves yourself, if you don''t already know.
The knight is given 3 moves and programmers have to produce the output
of all possible positions the knight can be at in 3 moves (where none
of these final positions could also be achieved in 2 moves eg moving 2
up 1 left and finally 1 right 2 down) in the form:
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
^
We use a hat to symbolise where the knight is and in my figure above,
that''s where the knight ALWAYS starts.
Now I know that there are a maximum of 8 ways a knight can move.
If I call topleft() where the knight moves 2 up 1 left, upleft() where
the knight moves 1 up 2 left, downleft() where the knight moves 1 down
2 left and btmleft 2 down 1 left (intuitively figuring out the
corresponding four) there are 8 functions representing a knight''s
possible movements.
Now I''m not gonna use letters and numbers for the coords of the
chessboard but rather x and y where the 1, 1 is the bottom left corner
of a chessboard. So I define a struct called co
struct co {
int x, y;
};
Each of the ''movement'' functions returns a struct co eg:
struct co topleft(int x, int y)
{
struct co temp;
if ( (x-1) >= 1 && (y+2) <= 8) {
temp.x = x;
temp.y = y;
return temp;
} else {
temp.x = 0;
temp.y = 0;
return temp;
}
}
In the main function I plan to create a temporary struct co and a
struct co array called pos with 40 elements which is probably a little
much.
So:
struct co temp;
struct co pos[40];
temp.x = 2;
temp.y = 1; /* where every knight starts */
temp = topleft(temp.x, temp.y);
if ( (temp.x != 0) && (temp.y != 0) ) {
temp = topleft(temp.x, temp.y);
if ( (temp.x != 0) && (temp.y != 0) )
temp = topleft(temp.x, temp.y);
if ( (temp.x != 0) && (temp.y != 0) )
pos[0] = temp;
}
temp.x = 2;
temp.y = 1;
/* etc. */
So it goes on an on: topleft, topleft, topleft
topleft, topleft, topright
topleft, topleft, upleft
But I could be writing over 1000 lines of code just for this program!
The competition only allowed and only allows 2 hours to do what you
can and submit your source code and executable via email to wherever
they collect it!
How do I better do this program? Have I got the gist of it? Any of it?
Bert
推荐答案
" Bert" < al ***************** @ gmail.comwrote in message
news：7e ************* ********************* @ q24g2000 prf.googlegroups.com ...
"Bert" <al*****************@gmail.comwrote in message
news:7e**********************************@q24g2000 prf.googlegroups.com...
这是一个来自编程比赛的过去的问题。
在棋盘上（8个方格，8个方格），骑士坐在b1上是b
从底行左侧2）。要削减废话，如果你还不知道的话，找出一个骑士如何移动自己的b
。
This is a past question from a programming competition.
On a chess board (8 squares by 8 squares), there''s is a knight sitting
on b1 (2 from the left of the bottom row). To cut the crap, find out
how a knight moves yourself, if you don''t already know.
但我可以为这个程序编写超过1000行代码！
竞赛只允许并且只允许2小时你可以做什么你可以通过电子邮件将你的源代码和可执行文件提交给他们收集它的地方
！
我该如何更好做这个程序？我有它的要点吗？任何一个？
But I could be writing over 1000 lines of code just for this program!
The competition only allowed and only allows 2 hours to do what you
can and submit your source code and executable via email to wherever
they collect it!
How do I better do this program? Have I got the gist of it? Any of it?
comp.programming可能会更好地发布到（虽然这里没有比
更活跃），因为这不是特别关于C. br />
然而，你的做法似乎并不合适。你从位置P
开始，然后你需要一个从那里扫描所有合法移动的功能（Q1，
Q2，... Qn）。对于每一个，例如。 Q1，你再次调用函数来获得
R1，R2等。
因此建议使用递归解决方案。一旦你获得第3步，你输出
的位置。
如果你只能访问每个方块一次（所以可能已经完成了）在第1次
或第二次移动），使用一个8x8 0'的数组，并在第一次访问一个方格
时标记为1。如果这是第一次访问，只继续使用正方形（计算从那里移动
或输出该位置）。
-
Bartc
comp.programming might be better to post to (although less active than
here), as this is not specifically about C.
However, your approach doesn''t seem quite right. You start at position P
then you need a function which scans through all legal moves from there (Q1,
Q2, ... Qn). For each of those, eg. Q1, you call the function again to get
R1, R2 etc.
So suggests a recursive solution. Once you''ve got the 3rd move, you output
the position.
If you can only visit each square once (so may have already been done on 1st
or 2nd move), use an array of 8x8 0''s, and mark 1 when you visit a square
for the first time. Only continue with a square (calculate moves from there
or output that position) if this is the first visit.
--
Bartc
" Bartc" < bc@freeuk.com写信息
新闻：Un ****************** @ text.news.virginmedia.co m ...
"Bartc" <bc@freeuk.comwrote in message
news:Un******************@text.news.virginmedia.co m...
>
" Bert" < al ***************** @ gmail.comwrote in message
news：7e ************* ********************* @ q24g2000 prf.googlegroups.com ...
>
"Bert" <al*****************@gmail.comwrote in message
news:7e**********************************@q24g2000 prf.googlegroups.com...
>这个来自编程竞赛的过去的问题。
在棋盘上（8个方格，8个方格），骑士坐在b1上（左边2个）底行）。要削减废话，找出一个骑士如何移动你自己，如果你还不知道。
>This is a past question from a programming competition.
On a chess board (8 squares by 8 squares), there''s is a knight sitting
on b1 (2 from the left of the bottom row). To cut the crap, find out
how a knight moves yourself, if you don''t already know.
>但我可以为这个程序编写超过1000行代码！
竞赛只允许，只允许2小时做你可以做的事情，并通过电子邮件将你的源代码和可执行文件提交给他们收集它的地方！
我该如何更好地完成这个程序？我有它的要点吗？任何一个？
>But I could be writing over 1000 lines of code just for this program!
The competition only allowed and only allows 2 hours to do what you
can and submit your source code and executable via email to wherever
they collect it!
How do I better do this program? Have I got the gist of it? Any of it?
哦，我会说，我很想用一个索引0..63
或1..64，而不是（1..8,1..8），因为它会简化一些事情
（在输出时转换回x，y）。我可能错了。
-
Bartc
Oh, and I was going to say, I would be tempted to simply use an index 0..63
or 1..64, rather than (1..8,1..8) because it would simplify some things
(convert back to x,y on output). I might be wrong though.
--
Bartc
Bert说：
Bert said:
这是编程竞赛的一个过去的问题。
在棋盘上（8个方格，8个方格），'''' s是骑士坐在b1上的
（底行左边2）。
This is a past question from a programming competition.
On a chess board (8 squares by 8 squares), there''s is a knight sitting
on b1 (2 from the left of the bottom row).
插入符号指向c1。我会假设你指的是正确的地方和
，你只是错误输入c1。
The caret points to c1. I''ll assume you are pointing to the right place and
that you merely mistyped c1.
骑士获得了3个动作，程序员必须产生输出
所有可能的位置，骑士可以在3个动作中进行（其中没有
这些最终位置也可以在2个动作中实现，例如移动2
向上1，最后1对2向下）形式：
OOOOOOOO
OOOOOOOO
OOOOOOOO
OOOOOOOO
OOOOOOOO
OOOOOOOO
OOOOOOOO
OOOOOOOO
^
The knight is given 3 moves and programmers have to produce the output
of all possible positions the knight can be at in 3 moves (where none
of these final positions could also be achieved in 2 moves eg moving 2
up 1 left and finally 1 right 2 down) in the form:
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
^
我们从分析开始。一举一动，他可以到达B：
OOOOOOOO
OOOOOOOO
OOOOOOOO
OOOOOOOO
OOOOOOOO
OBOBOOOO
BOOOBOOO
OOAOOOOO
两个移动，他可以到达C（但我们不会回到A或B）：
OOOOOOOO
OOOOOOOO
OOOOOOOO
COCOCOOO
OCOCOCOO
OBCBOOCO
BCOCBCOO
COAOCOCO
在三个动作中，他可以到达D（但我们不会回到A，B或C）：
OOOOOOOO
OXOXOXOO
XOXOXOXO
CXCXCXOX
XCXCXCXO
OBCBOXCX
BCXCBCXO
CXAOCXCX
用1代替所有X，用0代替非X给我们：
OOOOOOOO
O 1 O 1 O. 1 OO
1 O 1 O 1 O 1 O
0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
O 0 0 0 0 1 0 1
0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 1
程序现在很容易编写：只需打印上面的网格即可。
的表现应该令人印象深刻。如果你的确意味着b1而不是
c1，请相应调整解决方案。
We start with analysis. In one move, he can get to B:
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O O O O O O
O B O B O O O O
B O O O B O O O
O O A O O O O O
In two moves, he can get to C (but we won''t return to A or B):
O O O O O O O O
O O O O O O O O
O O O O O O O O
C O C O C O O O
O C O C O C O O
O B C B O O C O
B C O C B C O O
C O A O C O C O
In three moves, he can get to D (but we won''t return to A, B, or C):
O O O O O O O O
O X O X O X O O
X O X O X O X O
C X C X C X O X
X C X C X C X O
O B C B O X C X
B C X C B C X O
C X A O C X C X
Replacing all X with 1 and non-X with 0 gives us:
O O O O O O O O
O 1 O 1 O 1 O O
1 O 1 O 1 O 1 O
0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
O 0 0 0 0 1 0 1
0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 1
The program is now easy to write: simply printf the above grid. The
performance should be impressive. If you really did mean b1 rather than
c1, adjust the solution accordingly.
现在我不会用字母和数字对于
棋盘的坐标，而不是x和y，其中1,1是左下角
的棋盘。
Now I''m not gonna use letters and numbers for the coords of the
chessboard but rather x and y where the 1, 1 is the bottom left corner
of a chessboard.
你会发现0,0对阵列效果更好。
You''d find that 0, 0 works better with arrays.
每个' 'movement''函数返回一个struct co例如：
struct co topleft（int x，int y）
{
struct co temp;
if（（x-1）> = 1&&（y + 2）< = 8）{
temp.x = x;
temp.y = y;
返回临时;
Each of the ''movement'' functions returns a struct co eg:
struct co topleft(int x, int y)
{
struct co temp;
if ( (x-1) >= 1 && (y+2) <= 8) {
temp.x = x;
temp.y = y;
return temp;
这实际上是如何移动的？你不是指temp.x = x-1，temp.y =
y + 2？
< snip>
How does this actually move anything? Don''t you mean temp.x = x-1, temp.y =
y+2?
<snip>
但是我可以为这个程序编写超过1000行代码！
But I could be writing over 1000 lines of code just for this program!
1000行并不是那么多，真的。但是你不需要那么多
。
查找循环和东西。哦，和递归，在这种情况下。 （总是假设
你不想做快速简单的printf。）
-
Richard Heathfield < http://www.cpax.org.uk>
电子邮件：-http：// www。 + rjh @
谷歌用户：< http://www.cpax.org.uk/prg/writings/googly.php>
Usenet是一个奇怪的放置" - dmr 1999年7月29日
1000 lines isn''t all that many, really. But you don''t need that many
anyway.
Look up loops and stuff. Oh, and recursion, in this case. (Always assuming
you don''t want to do the quick and easy printf.)
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
这篇关于在3个动作中，骑士可以去哪里？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
