9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

迷宫问题



回专题模式 回学习阶段模式 【题目名称、来源】 迷宫问题 migong.pas{经典问题} 【问题描述】 如下图所示,迷宫可以划分为 n*m(n 行 m 列 4<=m,n<=20 有一个人可以向上、下、左、 右四个方向走,每一步走一格。现在从左上角(A 位置)向右下角(B 位置)走,但是他身 在迷宫当中,容易迷路,请你找出一条路能成功的从 A 走到 B。 A

>
B 输入数据: N M {以下 n 行 m 列数字以一个空格隔开,0 代表有路,1 代表障碍物} 00001 10111 10001 00101 00000 输出数据: {n*m 列数字,以一个空格隔开,0 代表路,1 代表障碍,2 代表走过的路} 20001 12111 12221 00121 00022 【所属专题】 回溯法 【适合学习阶段】 第一阶段、第二阶段 【解题思路】 问题分析: 存储结构: program migong; const h:array [1..4] of integer=(0,1,0,-1);{行位移常量数组} l:array [1..4] of integer=(1,0,-1,0);{列位移常量数组} var a:array [1..20,1..20] of integer;{迷宫 0 代表通路 1 代表障碍} step:array [1..100,1..2] of integer;{走过的路径记录} 【测试数据】

【源程序】 program migong; const h:array [1..4] of integer=(0,1,0,-1);{行位移常量数组} l:array [1..4] of integer=(1,0,-1,0);{列位移常量数组} var a:array [1..20,1..20] of integer;{迷宫 0 代表通路 1 代表障碍} i,j,n,m,count:integer; step:array [1..100,1..2] of integer;{走过的路径记录} procedure print;{打印} var i:integer; begin assign(output,'migong.out'); rewrite(output); for i:=1 to count do writeln('(',step[i,1],',',step[i,2],')'); readln; close(output); end; procedure run(i,j:integer);{递归程序 i,j 为当前位置} var i1,j1,r:integer; begin r:=0; while r<4 do begin inc(r); i1:=i+h[r];j1:=j+l[r];{试着向前走} if (i1>0) and(i1<=n)and(j1>0)and(j1<=m)and(a[i1,j1]=0) then begin {如果没有走出界,并且前面是没走过的通路} a[i1,j1]:=2; {向前走} count:=count+1; step[count,1]:=i1;step[count,2]:=j1;{记录下这一步} if (i1=n)and(j1=m) then begin print; halt; end else begin run(i1,j1) end; a[i1,j1]:=0;{回溯} count:=count-1; end; end; end;

begin assign(input,'migong.in'); reset(input); readln(n,m); for i:=1 to n do begin for j:=1 to m do read(a[i,j]); readln; end; count:=1;step[count,1]:=1;step[count,2]:=1; run(1,1); close(input); end.



更多相关文章:
迷宫问题描述与思想
迷宫求解 求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时,通常 用的是“穷举求解”的方法,即从入口出发,顺某一方向向前探索,若能...
迷宫问题求解
迷宫问题求解_IT/计算机_专业资料。问题描述:可以输入一个任意大小的迷宫数据,用非递归的方法求出一条走出迷宫的路径,并将路径输出;要求:在上交资料中请写明:存储...
迷宫问题——数据结构课程设计迷宫问题完整版(含源代码)
迷宫问题——数据结构课程设计迷宫问题完整版(含源代码)_计算机软件及应用_IT/计算机_专业资料。数据结构课程设计迷宫问题完整版(含源代码) ...
数据结构程序设计(迷宫问题)
合肥工业大学数据结构课程设计报告 课程设计名称:迷宫问题的数据结构 C++描述 班 级:信息与计算科学 1 班 姓 名:刘石清 张任重 20106583 20106607 指导 老师:王...
数据结构课程设计-迷宫问题
数据结构课程设计-迷宫问题_IT/计算机_专业资料。利用二维数组来表示迷宫,用1表示一堵墙,用0表示通路,为了不出界在迷宫的周围需添加一堵墙;先创建迷宫,然后给出...
迷宫问题算法实现
迷宫问题算法实现_计算机软件及应用_IT/计算机_专业资料。一、需求分析 本课程设计是解决迷宫求解的问题,从入口出发,顺某一方向向前探索,若能走通,则继续 往前走;...
数据结构 迷宫问题 课程设计报告格式
数据结构 C++课程设计一、设计题目 综合实验九一、 (1) (2) 实验目的: 迷宫问题 熟练掌握链栈的基本操作及应用。 利用链表作为栈的存储结构,设计实现一个求解...
迷宫问题实验报告
迷宫问题实验报告_计算机软件及应用_IT/计算机_专业资料。最好的数据结构迷宫问题实现报告,附带完整源程序,可直接上机运行武汉纺织大学数学与计算机学院 数据结构课程设...
c语言实现 迷宫问题
//di 是下一个相邻的可走的方位号 数据结构试验——迷宫问题 }st[MaxSize];// 定义栈 int top=-1 //初始化栈 3 设计运算算法要寻找一条通过迷宫的路径,...
迷宫问题的C,C++算法实现
迷宫问题的C,C++算法实现_计算机软件及应用_IT/计算机_专业资料。基于栈的 C 语言迷宫问题与实现一. 问题描述多年以来, 迷宫问题一直是令人感兴趣的题目。 实验心...
更多相关标签:
迷宫问题 数据结构    迷宫问题 java    迷宫    迷宫问题 c++    迷宫问题c语言    迷宫问题 华为oj    迷宫问题 bfs    八皇后问题    

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图