做一次伸手党。。。设计一个程序，没辙了，求提供思路

wyj915752168

伪代码，思路都可以。。。我们要求使用C，其他的高级语言，估计我也还看不懂

peng85344558

沙发我先坐了~~这一道题和当年参加CPC时候那道蜜粉采花蜜的原理，就我想到的思路，可以采用将格子化成点，对应1、2、……16，然后用运筹学的思路，1可以和2、5连接，2可以和3、5连接……画出一幅路线图（太久了图名早忘了）

例如说你想2x2的点就是6出发，那你就从6出发或者把6画到1的位置，然后依序做图解图就行了。。。解这个图就用到七桥的解决原理，是不是叫遍历我也不记得了，百度看看“七桥+运筹学”看看吧，最好是临时学下运筹学，它对于算法解决图形问题非常有帮助的~~代码不上了，依照这个思路编出代码不会很复杂的
ps：逻辑算法的精妙在于灵活用学过的思路，变动式解决问题~~有机会学学数学模型、运筹学这几门吧，这个图一看到就没了思路，数学底蕴有点不足~~

levibeta

遍历算法？

随便注册

每一步都向边界最近的方向走，走过的变为边界，就是贴边绕圈

loms126

先拿MATLAB写了一个，程序见附件：
使用最原始的递归，没有进行优化。
递归函数

1. function [OK_flag]=check_route(Matrix,now_x,now_y,remain_block_count)
   
2. global N route_x route_y
   
3. % figure(1)                                             %调试时用的，百分号为matlab注释标记
   
4. % cla
   
5. % plot(now_x,now_y,'.', 'MarkerSize',80)
   
6. % axis([1,N,-N,-1])
   
7. 
   
8. OK_flag=false;                        %C语言 放到最后，之前没有返回成功（true）时，返回该值              
   
9. if remain_block_count==0         %判断是否全部走完
   
10.     route_x=[route_x,now_x];    %将路径 倒序放回到route全局变量里
    
11.     route_y=[route_y,now_y];
    
12.     OK_flag=true;                    %返回成功
    
13.     return
    
14. end
    
15. %go up                                     %向上走，以下四个判断大同小异，对应不同方向
    
16. if (now_y>1) && ((Matrix(now_x,now_y-1))==1)     %不是最上边缘才能向上走，且上面的一格没走过
    
17.     next_x=now_x;                                      %下一步的坐标
    
18.     next_y=now_y-1;
    
19.     temp_Matrix=Matrix;    temp_Matrix(now_x,now_y)=0;      %缓存一下矩阵（下面还要用到，c里面注意直接赋值传递的是指针，需修改），当前点走过做标记
    
20.     [OK_flag]=check_route(temp_Matrix,next_x,next_y,remain_block_count-1); %递归
    
21.     if OK_flag            %判断是否全部走完，如果是，倒序添加路径，逐层向上返回
    
22.         route_x=[route_x,now_x];           %matlab支持矩阵拼接，C中需要根据remain_block_count的值，按数组序号赋值
    
23.         route_y=[route_y,now_y];
    
24.         return
    
25.     end
    
26. end
    
27. %go down
    
28. if (now_y<N) && ((Matrix(now_x,now_y+1))==1)
    
29.     next_x=now_x;
    
30.     next_y=now_y+1;
    
31.     temp_Matrix=Matrix;    temp_Matrix(now_x,now_y)=0;
    
32.     [OK_flag]=check_route(temp_Matrix,next_x,next_y,remain_block_count-1);
    
33.     if OK_flag
    
34.         route_x=[route_x,now_x];
    
35.         route_y=[route_y,now_y];
    
36.         return
    
37.     end
    
38. end
    
39. %left
    
40. if (now_x>1) && ((Matrix(now_x-1,now_y))==1)
    
41.     next_x=now_x-1;
    
42.     next_y=now_y;
    
43.     temp_Matrix=Matrix;    temp_Matrix(now_x,now_y)=0;
    
44.     [OK_flag]=check_route(temp_Matrix,next_x,next_y,remain_block_count-1);
    
45.     if OK_flag
    
46.         route_x=[route_x,now_x];
    
47.         route_y=[route_y,now_y];
    
48.         return
    
49.     end
    
50. end
    
51. %right
    
52. if (now_x<N) && ((Matrix(now_x+1,now_y))==1)
    
53.     next_x=now_x+1;
    
54.     next_y=now_y;
    
55.     temp_Matrix=Matrix;    temp_Matrix(now_x,now_y)=0;
    
56.     [OK_flag]=check_route(temp_Matrix,next_x,next_y,remain_block_count-1);
    
57.     if OK_flag
    
58.         route_x=[route_x,now_x];
    
59.         route_y=[route_y,now_y];
    
60.         return
    
61.     end
    
62. end
    
63. 
    
64. return

复制代码

---

主函数

1. global N
   
2. global route_x route_y
   
3. N=6;
   
4. Matrix=ones(N,N);               %生成 N*N,元素全是1的二维矩阵
   
5. start_x=1;                          %起始点 x y
   
6. start_y=1;
   
7. 
   
8. route_x=[];                        %清空路径
   
9. route_y=[];
   
10. 
    
11. [OK_flag]=check_route(Matrix,start_x,start_y,N*N-1)
    
12. route_x                    %输出路径
    
13. route_y

复制代码

先吃饭去了，注释一会补充。2:41PM补充注释。

wyj915752168

loms126 发表于 2013-3-22 13:50
先拿MATLAB写了一个，程序见附件：
使用最原始的递归，没有进行优化。
递归函数

---

真是辛苦了。。。虽然很内疚地说一声没有接触过MATLAB

loms126

wyj915752168 发表于 2013-3-22 13:52
真是辛苦了。。。

先简单写个注释把，否则看不懂。


Matrix是标记格点是否走过的矩阵，c里面用2维数组即可，数据类型可用Byte（？是这个吗），以减小内存使用。
全局变量route_x ，route_y标记路径，C里面请先申明，注意大小是N*N。
now_x,now_y为现在位于的格点。
remain_block_count为计数，用来判断是否全部走完。

OK_flag标记用来表示成功全部走完。


（余下吃完饭补充）

wyj915752168

loms126 发表于 2013-3-22 13:58
先简单写个注释把，否则看不懂。

谢谢，抱歉，实在是麻烦你了。。。

loms126

wyj915752168 发表于 2013-3-22 14:01
谢谢，抱歉，实在是麻烦你了。。。

已补充注释。

对于N为偶数，如下路径恒成立，不需要计算：


更数学的解法：
将格点染成国际象棋的棋盘，相邻格点的颜色互异。每走一步，颜色就会改变。
对于N为奇数，存在（N*N+1）/2个(奇数个)白格子和（N*N-1）/2个（偶数个）黑格子，全部走完需奇数步，而每走两步颜色复原。所以从任意黑格子开始走必然无法走完。可证明从任意白格子走可以走完。同理，N为偶数，从任意各自走可以走完。

算法上：
先判断N 的奇偶。为偶，按上图生成路径。为奇时，坐标X+Y为偶数的点可以走完，用最深优先搜索的四叉树求解（如上面matlab的算法），坐标X+Y为奇数时，无需搜索，必然无解。