洛谷1605 迷宫

本题地址： http://www.luogu.org/problem/show?pid=1605

题目背景

迷宫 【问题描述】 给定一个N*M方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和 终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫 中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。 输入样例 输出样例 【数据规模】 1≤N,M≤5

题目描述

输入输出格式

输入格式：

【输入】第一行N、M和T，N为行，M为列，T为障碍总数。第二行起点坐标SX,SY，终点坐标FX,FY。接下来T行，每行为障碍点的坐标。

输出格式：

【输出】给定起点坐标和终点坐标，问每个方格最多经过1次，从起点坐标到终点坐标的方案总数。

输入输出样例

输入样例#1：

2 2 1 1 1 2 2 1 2

输出样例#1：

1

题解

深搜DFS

纯回溯题。

先把障碍标记好，然后从起点开始，往下DFS，当遇到障碍或走到边界时，返回上一层，继续往另一个方向走。

当到达终点时，将方案数+1，继续过程，直到结束。

PS：

DFS就是这样一种走不通就掉头的搜索模式。虽然比较耗时，但在缺乏有效方法是，DFS也不失为一种选择。

搜索也是一种很万能的解题方法，好多题都可以用它来解决（虽然不一定是最优方案）。

下面附上代码。

代码

program d1;    var    a,d:array[1..1000,1..1000] of longint;    b,c:array[1..4] of longint;    n,m,l,p,x,y,f,k,i:longint;    procedure sou(x,y:longint);           //深搜    var    i:longint;    begin    if a[x,y]=1 then begin         f:=f+1;        exit;    end;    for i:=1 to 4 do        if (x+b[i]>0) and (x+b[i]<=n) and (y+c[i]>0) and (y+c[i]<=m) and (a[x+b[i],y+c[i]]<>2) and (d[x+b[i],y+c[i]]<>1)then begin            d[x+b[i],y+c[i]]:=1;        sou(x+b[i],y+c[i]);            d[x+b[i],y+c[i]]:=0;        end;    end;    begin    readln(n,m,k);    readln(x,y,l,p);    a[l,p]:=1;    for i:=1 to k do        begin        read(l,p);    a[l,p]:=2;    end;    b[1]:=1;    c[1]:=0;    b[2]:=0;    c[2]:=1;    b[3]:=-1;    c[3]:=0;    b[4]:=0;    c[4]:=-1;   //方位    d[x,y]:=1;   //初始化    sou(x,y);    write(f);    end.    

（本文系笔者原创，未经允许不得转载）

转载于:https://www.cnblogs.com/yzm10/p/4751983.html