这种东西是图论题:列出所有状态,列出所有合法的状态转移,求给定两结点间的通路..
示范下..首先这里的状态我们用七元组[a,b,c,d,e,f,g](0<=a,b,c,d,f<=1,0<=e,g<=2)表示,其中a,b,c,d,e,f,g分别表示"左岸"的船,猎人,狼,男人,男人孩子,女人,女人孩子的数量.于是总共有2^5*3^2=288种状态.
其中各种会死人的限制对应b=0 and c=1 and d+e+f+g>0,b=1 and c=0 and d+e+f+g<6,d=0 and e>0 and f=1,d=1 and e<2 and f=0,d=1 and f=0 and g>0,d=0 and f=1 and g<2,经筛选,288种状态中有且仅有84种不触犯这些限制.
然后表示出状态转移.显然[1,b,c,d,e,f,g]可转移到的状态有[0,b-1,c,d,e,f,g],[0,b-1,c-1,d,e,f,g],[0,b-1,c,d-1,e,f,g],[0,b-1,c,d,e-1,f,g],[0,b-1,c,d,e,f-1,g],[0,b-1,c,d,e,f,g-1],[0,b,c,d-1,e,f,g],[0,b,c-1,d-1,e,f,g],[0,b,c,d-1,e-1,f,g],[0,b,c,d-1,e,f-1,g],[0,b,c,d-1,e,f,g-1],[0,b,c,d,e,f-1,g],[0,b,c-1,d,e,f-1,g],[0,b,c,d,e-1,f-1,g],[0,b,c,d,e,f-1,g-1],而[0,b,c,d,e,f,g]可转移到的状态有[1,b+1,c,d,e,f,g],[1,b+1,c+1,d,e,f,g],[1,b+1,c,d+1,e,f,g],[1,b+1,c,d,e+1,f,g],[1,b+1,c,d,e,f+1,g],[1,b+1,c,d,e,f,g+1],[1,b,c,d+1,e,f,g],[1,b,c+1,d+1,e,f,g],[1,b,c,d+1,e+1,f,g],[1,b,c,d+1,e,f+1,g],[1,b,c,d+1,e,f,g+1],[1,b,c,d,e,f+1,g],[1,b,c+1,d,e,f+1,g],[1,b,c,d,e+1,f+1,g],[1,b,c,d,e,f+1,g+1](当然,取其中满足上述的定义域和不死人条件的限制的部分).
现在我们得到了一个图(一般而言是有向图,但一般见到的题无向图足矣).已知起点和终点,求是否连通,以及连通时求一条或所有最短通路..可以上算法了..(双向)bfs..
答案是17.
下面上图..我就不说今天码这么细只是因为最近点了个画这种图的技能而已了..
此渡河问题的状态转移(仅合法状态,省略20个无法转移的状态) |
