很简单啊。。2商人1随从,回来1商人;两商人一随从,回来两随从;三随从

1楼 @sshic 哈哈 第一步就挂了

这样应该是对的

0表示强盗 1表示商人

------ --- 000111
------ 01- 0011-- <----
01---- --- 0011--
0----- 1-- 0011-- ---->
0----- --- 00111-
0----- 00- 111--- <----
000--- --- 111---
00---- 0-- 111--- ---->
00---- --- 0111--
00---- 11- 01---- <----
0011-- --- 01----
01---- 01- 01---- ---->
01---- --- 0011--
01---- 11- 00---- <----
0111-- --- 00----
111--- 0-- 00---- ---->
111--- --- 000---
111--- 00- 0----- <----
11100- --- 0-----
1110-- 0-- 0----- ---->
1110-- --- 00----
1110-- 00- ------ <----
111000 --- ------

广搜应该一下就出来了

3楼 @adad184 仆人很听话啊。

3楼 @adad184 你的结果是对的,但是过程冗余,有很大的优化余地,先做到目的地111出发地000可以节省很多步骤

5楼 @forzaJuve 我写了个程序跑 貌似应该是最优解之一

5楼 @forzaJuve 简单写了个广搜 看看哪不对?

#define MAXCOUNT 3
bool canPass(int dstS, int dstM, int srcS, int srcM)
{
 if((dstS<0) || (dstS>MAXCOUNT) ||
 (dstM<0) || (dstM>MAXCOUNT) ||
 (srcS<0) || (srcS>MAXCOUNT) ||
 (srcM<0) || (srcM>MAXCOUNT))
 {
 return false;
 }
 if( (dstS>dstM) && (dstM!=0) )
 {
 return false;
 }
 if( (srcS>srcM) && (srcM!=0) )
 {
 return false;
 }
 return true;
}
- (void) calc
{
 int stack[100000] = {0};
 int index[100000] = {0};
 int solution[1000000] = {0};
 index[0] = -1;
 stack[0] = MAXCOUNT*11;
 solution[stack[0]] = 1;
 int v[5][2] = {{0,1},{1,1},{1,0},{0,2},{2,0}};
 int indexBeg = 0;
 int indexEnd = 1;
 int level = 0;
 bool run = true;
 int count = 0;
 while ( run )
 {
 int iBeg = indexEnd;
 int iEnd = indexEnd;
 int m = (level%2==0)?1:-1;
 for ( int i = indexBeg ; i < indexEnd ; ++i )
 {
 int dstS = stack[i]/1000;
 int dstM = (stack[i]/100)%10;
 int srcS = (stack[i]/10)%10;
 int srcM = stack[i]%10;
 if ( stack[i] == 1100*MAXCOUNT )
 {
 printf("find! count %d level %dn",++count, level);
 int idx = i;
 while ( index[idx] >= 0 )
 {
 printf ("%04dn",stack[idx]);
 idx = index[idx];
 }
 continue;
 }
 for ( int j = 0 ; j < 5 ; ++j )
 {
 int newDstS = dstS + m*v[j][0];
 int newDstM = dstM + m*v[j][1];
 int newSrcS = srcS - m*v[j][0];
 int newSrcM = srcM - m*v[j][1];
 int sol = newDstS*1000+newDstM*100+newSrcS*10+newSrcM;
 if ((solution[sol+((level%2==0)?0:10000)]!=0) &&
 (solution[sol+((level%2==0)?0:10000)]<level))
 {
 continue;
 }
 if ( canPass(newDstS, newDstM, newSrcS, newSrcM) )
 {
 stack[iEnd] = sol;
 index[iEnd] = i;
 if ( sol != 1100*MAXCOUNT )
 {
 solution[sol+((level%2==0)?0:10000)] = level;
 }
 ++iEnd;
 }
 }
 }
 if ( iBeg == iEnd )
 {
 run = false;
 continue;
 }
 indexBeg = iBeg;
 indexEnd = iEnd;
 ++level;
 }
 printf("done at level:%d",level);
}

找到4个解 但是都需要11步

find! count 1 level 11
3300
2211
2310
0330
1320
1122
2211
2013
3003
1023
1122
find! count 2 level 11
3300
1320
2310
0330
1320
1122
2211
2013
3003
1023
1122
find! count 3 level 11
3300
2211
2310
0330
1320
1122
2211
2013
3003
1023
2013
find! count 4 level 11
3300
1320
2310
0330
1320
1122
2211
2013
3003
1023
2013
done at level:11

商仆go,商back,2仆go,仆back,2商go,商仆back,2商go,仆back,2仆go,仆back,2仆go。

7楼 @adad184

1,一个商人一个随从过去一个商人回来。

2,两个随从过去一个随从回来。

此时一岸三商一随,另一岸两随。

3,两商过岸,一商一随从回来。

4,两商过岸,一随从回来。

此时一岸三随,另一岸三商。

5,两随过岸,一随回来再接最后一随过岸。

9楼 @forzaJuve 这.. 跟我的答案不是一模一样吗?....