回 帖 发 新 帖 刷新版面

主题:[讨论]202:堆栈出错(大虾帮忙)

我写了一个程序,原来输入:
5
0 0 0 0 0
1 1 1 0 1
1 0 0 0 0
0 0 1 1 0
0 0 0 0 0
后输出应该是:
(1,1)->(1,2)->(1,3)->(1,4)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)
可电脑总告诉我:202:堆栈出错,哪为大虾教教我,仔细说明一下关与202:堆栈出错的问题。这是我的程序:
const
        x1:array[1..4] of integer=(1,-1,0,0);
        y1:array[1..4] of integer=(0,0,1,-1);
var
        a:array[0..101,0..101] of integer;
        sc:array[1..1000] of integer;
        n,i,j,k:integer;
procedure dfs(x,y:integer);
begin
        for i:=1 to 4 do
        begin
                if a[x+x1[i],y+y1[i]] <>1 then
                begin
                        dfs(x+x1[i],y+y1[i]);
                        k:=k+1;
                        sc[k]:=i+x1[i];
                        k:=k+1;
                        sc[k]:=j+y1[i];
                end;
        end;
                if (x+x1[i])*(y+y1[i])=n*n then exit;
end;

begin
        read(n);
        fillchar(a,sizeof(a),1);
        for i:=1 to n do
                for j:=1 to n do
                        read(a[i,j]);
        dfs(1,1);
        for i:=k downto 1 do
        begin
                if 1=1 then
                begin
                        write(sc[1]);
                        break;
                end;
                if k mod 2=1 then
                        write(sc[i],',')
                else
                        write(sc[i],'->');
        end;

end.

FP提示我第9行和第14行出错,能帮我改一下吗?(编译没问题)。
这题原来是迷宫问题:给出一个n×n的迷宫,请你给出一条从入口(1,1)到出口(n,n)的路径。
输入数据:n和迷宫初始状态
输出数据:任意一条可行的路径
输入样例:
5
0 0 0 0 0
1 1 1 0 1
1 0 0 0 0
0 0 1 1 0
0 0 0 0 0
(如图)
输出样例:
(1,1)->(1,2)->(1,3)->(1,4)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)

回复列表 (共7个回复)

沙发

const
        x1:array[1..4] of integer=(1,-1,0,0);
        y1:array[1..4] of integer=(0,0,1,-1);
var
        a:array[0..101,0..101] of integer;
        sc,so:array[1..1000] of integer;
        n,i,j,k,l:integer;
procedure dfs(x,y:integer);
begin
  if (x=n) and (y=n) then if k<l then
   begin sc:=so; l:=k; end;
  for i:=1 to 4 do begin
    if a[x+x1[i],y+y1[i]]=0 then begin
      k:=k+1; so[k]:=x;
      k:=k+1; so[k]:=y;
      a[x,y]:=2;
      dfs(x+x1[i],y+y1[i]);
      k:=k-2; a[x,y]:=0;
    end;
  end;
end;

begin
  read(n);
  fillchar(a,sizeof(a),1);
  for i:=1 to n do
   for j:=1 to n do
    read(a[i,j]);
  k:=0; l:=1000; dfs(1,1);
  for i:=1 to l do begin
    write('(',sc[i],',',sc[i+1],')');
    if i+1<l then write('->') else
    write('->(',n,',',n,')');
    i:=i+1;
  end;
end.

板凳

哦~
你是没用一个数组存储某一个点是否被重复走哦
如果没判断的话就会兜圈子。。晕

3 楼


还是有点错啊,能不能讲一下思路?

4 楼

关键部分:
procedure dfs(x,y:integer);
begin
  if (x=n) and (y=n) then if k<l then
   begin sc:=so; l:=k; end;
  for i:=1 to 4 do begin
    if a[x+x1[i],y+y1[i]]=0 then begin
      k:=k+1; so[k]:=x;
      k:=k+1; so[k]:=y;
      
      used[x,y]:=true;

      a[x,y]:=2;
      dfs(x+x1[i],y+y1[i]);

      used[x,y]:=false;

      k:=k-2; a[x,y]:=0;
    end;
  end;
end;
还有,used数组初值全部为false,表示没走过;
开头的var里面我就先不写了,,,记得加上去:
used:array [1..101,1..101] of boolean;
就OK了

以上。

5 楼

如果没有判断的话会递归过深,建议用dfs(depth:integer)写比较顺

6 楼

等等先,果真是有点问题:
procedure dfs(x,y:integer);

var i:integer;

即是:把过程里的i定义为局部变量,否则答案会有问题。。
PS:如果你想问原来主程序的i咋办?
ANS:那就把原来的i改为ii就行了。

7 楼

递归错误

我来回复

您尚未登录,请登录后再回复。点此登录或注册