北大ACM3984,请告诉我下面的代码,我打出问号标记出来的那一段是什么意思.原题Time Limit:1000MS Memory Limit:65536K Total Submissions:1979 Accepted:1132 Description定义一个二维数组：int maze[5][5] = {0,1,0,0,0,0,1,0,
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/25 18:07:51
北大ACM3984,请告诉我下面的代码,我打出问号标记出来的那一段是什么意思.原题Time Limit:1000MS Memory Limit:65536K Total Submissions:1979 Accepted:1132 Description定义一个二维数组：int maze[5][5] = {0,1,0,0,0,0,1,0,
北大ACM3984,请告诉我下面的代码,我打出问号标记出来的那一段是什么意思.
原题
Time Limit:1000MS Memory Limit:65536K
Total Submissions:1979 Accepted:1132
Description
定义一个二维数组：
int maze[5][5] = {
0,1,0,0,0,
0,1,0,1,0,
0,0,0,0,0,
0,1,1,1,0,
0,0,0,1,0,
};
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线.
Input
一个5 × 5的二维数组,表示一个迷宫.数据保证有唯一解.
Output
左上角到右下角的最短路径,格式如样例所示.
Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
Sample Output
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)
Source
代码：
#include
#include
char d[100];
int a[7][7],c[7][7],minn;
int b[5][5];
int moves[4][2]={{0,-1},{-1,0},{0,1},{1,0}};/*显示*/
void display()
{
int i,j;
for(i=0;i
北大ACM3984,请告诉我下面的代码,我打出问号标记出来的那一段是什么意思.原题Time Limit:1000MS Memory Limit:65536K Total Submissions:1979 Accepted:1132 Description定义一个二维数组：int maze[5][5] = {0,1,0,0,0,0,1,0,
每走一个格加多少并不重要,这个值即表示了每一个步的开销,如果题中指定了每一步的开销,就按题中说的值来加,否则,只要其值能保证计算的正确性就行,对本题来说,minn的初值为25,当然每次加的量不能使最终的最短距离比minn还大.LZ标记问号的部分确实冗余,没有必要这样写,把 count++;和 count--;去掉即可.
这段代码中,tyr函数没有进行任何有效剪枝,这样的话该函数在数据量较大时将无法工作,所以可以稍加优化：使用一个数组记录当前已知的点到左上角的距离,每递归到达一个点,均与该数组中相应的位置比较,如果比之小,则更新该数组,并递归,否则就剪枝.每一步都可能有4种分支,每次递归记录下各自的选择,这样在获取更优解时就把当前的选择序列记录下来,就是最终最优解的选择序列.