（理工类）寒武能够到找到艾莉吗？

944f4fe875fb39d

原题来自：http://cnc.readfree.net/bbs/read.php?tid=4555735



用高速计算机计算的，

游客，本帖隐藏的内容需要积分高于 1000 才可浏览，您当前积分为 0

e, w, n, s, t, b 分别表示红心朝东西北南上下。

第二种能走到终点的走法是，

tV  s>  s>  sV  s>  s>  s>  sV
sV  bA  w<  bV  bA  eV  b<  bV
bV  b>  wA  n>  nA  eV  nA  n<
n>  nA  eV  b<  w<  e>  b>  wV
eV  b<  e>  bV  wA  eV  b<  w<
eV  nA  n<  n<  wA  eV  s>  sV
e>  b>  wV  b>  wA  e>  bA  bV
e0  b<  w<  nA  n<  n<  n<  n<

但红心向东。

没有别的走法。

先前的编程错误是，当到达终点时，红心不能向上的限制没有去掉。

944f4fe875fb39d

#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;
}

linsi

book 老师就是强，：）
此帖从一开始就注定必将成为经典，

hanvool

引用第37楼ly188于2007-12-21 23:32发表的 :
好不容易通关了~累死我了,最后关到比前面简单多了
寒武太苯了 6面都涂上心就好了么

知不知道 苯 有强致癌作用哇

磁铁

哈哈，bookish的第一个图完全正确。此题目只有唯一解，开始我也晕了
如果换成从对角走到对角，则本题无解。此题目前身源自一个普通理发师发明的游戏，欢迎大家继续解答，原创有想法有内容的文章将被推荐给学术妙笔版块，有机会获得威望

yzh_nj_china

此题目只有唯一解！！！！！

我的神啊~~~~
做对的又都是世上只有4个人能做对了~~~~

killl

看来我是没有希望作对了，怎么这么难，竟然用了编程，不得不服

ly188

似乎只能用算法解决
我的思路 下面分别代表朝某方向转的两张表
右左 0 1 * 2 3 * (1)
下上 0 * 1 2 * 3 (2)
每次向右或者向左(1)值递加或递减,如果(1)遇到*则(1)(2)不变
每次向下或者向上(2)值递加或递减,如果(2)遇到*则(1)(2)不变
0 0 即是红心向上,不晓得对不

yzh_nj_china

引用第48楼ly188于2007-12-22 12:11发表的 :
似乎只能用算法解决
我的思路 下面分别代表朝某方向转的两张表
右左 0 1 * 2 3 * (1)
下上 0 * 1 2 * 3 (2)
每次向右或者向左(1)值递加或递减,如果(1)遇到*则(1)(2)不变
.......

这个算下来应该比book老师的算的快一点，那for嵌套的计算量太大了~~~

ly188

游客，本帖隐藏的内容需要积分高于 1000 才可浏览，您当前积分为 0

yzh_nj_china

谁会编这样的程序：
ly188兄是两个表，谁能编出三个表的。
记有红心的是1，对应红心的面是-1，
然后红心的南北面为1和-1，东西面也是1和-1，这样的好处就是直接可以按加和算~~
初始条件是（1，0，0）经过几次循环后，最后又变回了（1，0，0）
~~~~
来了着才发现自己是菜鸟~~

看大侠们编~~~
看了book老师编的穷举情况的方法，虽然感觉好像简化了不少，但总感到什么地方不对劲~~好像又没有简化~~~只是直觉~~

ly188

发现错误一堆,我再仔细看看

bookish

不好意思，我本来以为这个问题已经解决了，所以写了个续集。

昨天用主ID进来（看得见各位的加密），才发现原来还没有解决，所以得赶紧帮寒武一个忙，简单写了一个程序，完全是穷举，因为我那时正在大型并行高速计算机上，所以根本不考虑速度。

第一次算出的结果是我给出的第二个，唯一的结果，但是还不符合条件。

检查程序后发现，我忘了把到达终点时红心不能向上的限制去掉，把这个结果去掉之后，就得到了那个唯一正确的结果了。

计算时间大约十几秒钟！所以，我的程序在PC机上是不能运行的。

在PC机上编程，还需要简化问题和减少计算量。请画出平面图仔细考虑。

bookish

引用第49楼yzh_nj_china于2007-12-22 12:38发表的 :
这个算下来应该比book老师的算的快一点，那for嵌套的计算量太大了~~~

我的那个算法，for嵌套的计算量不大，要命的是 goto L_0，这个问题可能的走法太多，我没有统计这个数字，goto L_0 至少是千万次。

我在编程前先按编程思路手算了二十几步（这是我的编程习惯，用来了解问题的性质），手算是从目的地倒算的（本想用动态规划法，所以倒过来做），编程时是从起点出发，因为正走倒走一样。

还可以增加很多走法失败的判别条件，比如，当达到右边界时，就只能向下走，到达上边界就只能向右走，到达下边界就只能向左走，到达左边界就只能向下走，等等，我手算时用这些条件，编程就不考虑了。

但如果用PC机，这些限制条件考虑的越多，需要试探的可能的走法就越少，计算速度就越快。

bookish

引用第44楼磁铁于2007-12-22 11:14发表的 :
........此题目只有唯一解

一个极为重要的提示。

根据这个提示，晚上我要试试看能否用PC机解决这个问题。

呵呵，又是一个挑战！

ly188

游客，本帖隐藏的内容需要积分高于 1000 才可浏览，您当前积分为 0

ly188

算错了~

磁铁

好的，画好我先把两位的妙笔乾坤大挪移到学术区

ly188

算法在很多地方还能改进

磁铁

辛苦费，晕倒，ly这个图和正确答案不一样，这样到最后那里小红心不是向上的。
Ａ点小红心向上，最后城堡小红心向上，其它时候小红心不能向上

谁能帮我演绎一下ly花心大萝卜的程序？谢谢！