（理工类）寒武能够到找到艾莉吗？
原题来自：http://cnc.readfree.net/bbs/read.php?tid=4555735http://cnc.readfree.net/bbs/p_w_upload/Mon_0712/51_7064_58bfdb181272d19.gif
用高速计算机计算的，
**** Hidden Message *****
e, w, n, s, t, b 分别表示红心朝东西北南上下。
第二种能走到终点的走法是，
tVs>s>sVs>s>s>sV
sVbAw<bVbAeVb<bV
bVb>wAn>nAeVnAn<
n>nAeVb<w<e>b>wV
eVb<e>bVwAeVb<w<
eVnAn<n<wAeVs>sV
e>b>wVb>wAe>bAbV
e0b<w<nAn<n<n<n<
但红心向东。
没有别的走法。
先前的编程错误是，当到达终点时，红心不能向上的限制没有去掉。
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
// free=0, e=1, w=2, n=3, s=4, t=5, b=6
// move e(right)=1, w(left)=2, n(up)=3, s(down)=4
int position(int mp, int direction)
{
short int n[ 6][ 4] = {6, 5, 1, 1, 5, 6, 2, 2, 3, 3, 6, 5, 4, 4, 5, 6, 1, 2, 3, 4, 2, 1, 4, 3};
return n[ mp - 1][ direction - 1];
}
#define MM 1000
short int t[ MM][ 8][ 8], u[ MM][ 8][ 8], v[ 8][ 8], ti[ MM], tj[ MM];
int main (void)
{
int i, j, k, n, n_new, mp, mp_new;
n = 0;
ti[ n] = tj[ n] = 0;
for (i = 0; i < 8; i++) for (j = 0; j < 8; j++) t[ n][ i][ j] = u[ n][ i][ j] = 0;
t[ 0][ 0][ 0] = 5;
L_0:
n_new = n;
mp = t[ n][ ti[ n]][ tj[ n]];
// right
mp_new = position(mp, 1);
if (tj[ n] < 7) if (!t[ n][ ti[ n]][ tj[ n] + 1]) if (mp_new != 5)
{
n_new++;
for (i = 0; i < 8; i++) for (j = 0; j < 8; j++)
{
t[ n_new][ i][ j] = t[ n][ i][ j];
u[ n_new][ i][ j] = u[ n][ i][ j];
}
ti[ n_new] = ti[ n];
tj[ n_new] = tj[ n] + 1;
t[ n_new][ ti[ n_new]][ tj[ n_new]] = mp_new;
u[ n_new][ ti[ n_new]][ tj[ n_new]] = 1;
}
// left
mp_new = position(mp, 2);
if (tj[ n]) if (!t[ n][ ti[ n]][ tj[ n] - 1]) if (mp_new != 5 || (ti[ n] == 7 && tj[ n] == 1))
{
n_new++;
for (i = 0; i < 8; i++) for (j = 0; j < 8; j++)
{
t[ n_new][ i][ j] = t[ n][ i][ j];
u[ n_new][ i][ j] = u[ n][ i][ j];
}
ti[ n_new] = ti[ n];
tj[ n_new] = tj[ n] - 1;
t[ n_new][ ti[ n_new]][ tj[ n_new]] = mp_new;
u[ n_new][ ti[ n_new]][ tj[ n_new]] = 2;
}
// upword
mp_new = position(mp, 3);
if (ti[ n]) if (!t[ n][ ti[ n] - 1][ tj[ n]]) if (mp_new != 5)
{
n_new++;
for (i = 0; i < 8; i++) for (j = 0; j < 8; j++)
{
t[ n_new][ i][ j] = t[ n][ i][ j];
u[ n_new][ i][ j] = u[ n][ i][ j];
}
ti[ n_new] = ti[ n] - 1;
tj[ n_new] = tj[ n];
t[ n_new][ ti[ n_new]][ tj[ n_new]] = mp_new;
u[ n_new][ ti[ n_new]][ tj[ n_new]] = 3;
}
// downword
mp_new = position(mp, 4);
if (ti[ n] < 7) if (!t[ n][ ti[ n] + 1][ tj[ n]]) if (mp_new != 5 || (ti[ n] == 6 && tj[ n] == 0))
{
n_new++;
for (i = 0; i < 8; i++) for (j = 0; j < 8; j++)
{
t[ n_new][ i][ j] = t[ n][ i][ j];
u[ n_new][ i][ j] = u[ n][ i][ j];
}
ti[ n_new] = ti[ n] + 1;
tj[ n_new] = tj[ n];
t[ n_new][ ti[ n_new]][ tj[ n_new]] = mp_new;
u[ n_new][ ti[ n_new]][ tj[ n_new]] = 4;
}
if (n_new > n)
{
for (k = n; k < n_new; k++) for (i = 0; i < 8; i++) for (j = 0; j < 8; j++)
{
t[ k][ i][ j] = t[ k + 1][ i][ j];
u[ k][ i][ j] = u[ k + 1][ i][ j];
ti[ k] = ti[ k + 1];
tj[ k] = tj[ k + 1];
}
n = n_new - 1;
if (n > MM - 4)
{
printf("not finifshed\n");
return 0;
}
goto L_0;
}
for (i = 0; i < 8; i++) for (j = 0; j < 8; j++) if (!t[ n][ i][ j])
{
n--;
if (n >= 0) goto L_0;
else return 0;
}
if (ti[ n] == 7 && tj[ n] == 0) // && t[ n][ i][ j] == 5)
{
for (i = 0; i < 8; i++) for (j = 0; j < 8; j++)
{
if (u[ n][ i][ j] == 1) v[ i][ j - 1] = 1;
else if (u[ n][ i][ j] == 2) v[ i][ j + 1] = 2;
else if (u[ n][ i][ j] == 3) v[ i + 1][ j] = 3;
else if (u[ n][ i][ j] == 4) v[ i - 1][ j] = 4;
}
v[ ti[ n]][ tj[ n]] = 0;
for (i = 0; i < 8; i++)
{
for (j = 0; j < 8; j++) printf("%d-%d ", t[ n][ i][ j], v[ i][ j]);
printf("\n");
}
printf("\n");
}
n--;
if (n >= 0) goto L_0;
return 0;
} book 老师就是强，：）
此帖从一开始就注定必将成为经典， 引用第37楼ly188于2007-12-21 23:32发表的 :
好不容易通关了~累死我了,最后关到比前面简单多了
寒武太苯了 6面都涂上心就好了么
知不知道 苯 有强致癌作用哇 哈哈，bookish的第一个图完全正确。此题目只有唯一解，开始我也晕了
如果换成从对角走到对角，则本题无解。此题目前身源自一个普通理发师发明的游戏，欢迎大家继续解答，原创有想法有内容的文章将被推荐给学术妙笔版块，有机会获得威望 此题目只有唯一解！！！！！
我的神啊~~~~
做对的又都是世上只有4个人能做对了~~~~ 看来我是没有希望作对了，怎么这么难，竟然用了编程，不得不服 似乎只能用算法解决
我的思路 下面分别代表朝某方向转的两张表
右左 0 1 * 2 3 * (1)
下上 0 * 1 2 * 3 (2)
每次向右或者向左(1)值递加或递减,如果(1)遇到*则(1)(2)不变
每次向下或者向上(2)值递加或递减,如果(2)遇到*则(1)(2)不变
0 0 即是红心向上,不晓得对不 引用第48楼ly188于2007-12-22 12:11发表的 :
似乎只能用算法解决
我的思路 下面分别代表朝某方向转的两张表
右左 0 1 * 2 3 * (1)
下上 0 * 1 2 * 3 (2)
每次向右或者向左(1)值递加或递减,如果(1)遇到*则(1)(2)不变
.......
这个算下来应该比book老师的算的快一点，那for嵌套的计算量太大了~~~ **** Hidden Message ***** 谁会编这样的程序：
ly188兄是两个表，谁能编出三个表的。
记有红心的是1，对应红心的面是-1，
然后红心的南北面为1和-1，东西面也是1和-1，这样的好处就是直接可以按加和算~~
初始条件是（1，0，0）经过几次循环后，最后又变回了（1，0，0）
~~~~
来了着才发现自己是菜鸟~~
看大侠们编~~~
看了book老师编的穷举情况的方法，虽然感觉好像简化了不少，但总感到什么地方不对劲~~好像又没有简化~~~只是直觉~~
发现错误一堆,我再仔细看看 不好意思，我本来以为这个问题已经解决了，所以写了个续集。
昨天用主ID进来（看得见各位的加密），才发现原来还没有解决，所以得赶紧帮寒武一个忙，简单写了一个程序，完全是穷举，因为我那时正在大型并行高速计算机上，所以根本不考虑速度。
第一次算出的结果是我给出的第二个，唯一的结果，但是还不符合条件。
检查程序后发现，我忘了把到达终点时红心不能向上的限制去掉，把这个结果去掉之后，就得到了那个唯一正确的结果了。
计算时间大约十几秒钟！所以，我的程序在PC机上是不能运行的。
在PC机上编程，还需要简化问题和减少计算量。请画出平面图仔细考虑。 引用第49楼yzh_nj_china于2007-12-22 12:38发表的 :
这个算下来应该比book老师的算的快一点，那for嵌套的计算量太大了~~~
我的那个算法，for嵌套的计算量不大，要命的是 goto L_0，这个问题可能的走法太多，我没有统计这个数字，goto L_0 至少是千万次。
我在编程前先按编程思路手算了二十几步（这是我的编程习惯，用来了解问题的性质），手算是从目的地倒算的（本想用动态规划法，所以倒过来做），编程时是从起点出发，因为正走倒走一样。
还可以增加很多走法失败的判别条件，比如，当达到右边界时，就只能向下走，到达上边界就只能向右走，到达下边界就只能向左走，到达左边界就只能向下走，等等，我手算时用这些条件，编程就不考虑了。
但如果用PC机，这些限制条件考虑的越多，需要试探的可能的走法就越少，计算速度就越快。 引用第44楼磁铁于2007-12-22 11:14发表的 :
........此题目只有唯一解
一个极为重要的提示。
根据这个提示，晚上我要试试看能否用PC机解决这个问题。
呵呵，又是一个挑战！ **** Hidden Message ***** 算错了~
好的，画好我先把两位的妙笔乾坤大挪移到学术区 算法在很多地方还能改进 辛苦费，晕倒，ly这个图和正确答案不一样，这样到最后那里小红心不是向上的。
Ａ点小红心向上，最后城堡小红心向上，其它时候小红心不能向上
谁能帮我演绎一下ly花心大萝卜的程序？谢谢！
页:
[1]
2