Java教程

【练习回顾】dfs迷宫+路径打印

本文主要是介绍【练习回顾】dfs迷宫+路径打印,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

很直接的dfs。递归+栈——不知道以后会不会生疏
进入一次dfs,相当于走一步,入栈;结束一次dfs,相当于这一步考虑结束,出栈
笑死,y1竟然是一个函数

题目描述

输入一个n*m的01矩阵作为01迷宫,并给定他的起点与终点,求出他不同逃跑路线的数目(不同逃跑路线中可以有相同的部分,但是不能完全相同)。

输入格式

前两行输入两个整数n和m(n、m均为正整数并且小于等于7),分别代表01矩阵行数和列数。接下来的n*m行,每行输入1个整数(0或1),对应着01矩阵各个元素值(按行输入)。接下来的四行分别代表迷宫的起点和终点,每行一个整数,分别代表起点与终点行数和列数。

输出格式

输出每种走法的路径。最终输出一个整数,代表逃跑路线的数目。

#include<stdio.h>
#include<string.h>

int N,M;
int map[8][8];
int x1,y1,x2,y2;
int cnt = 0;
char stack[100][30];
int top = -1;

int isAble(int x, int y){ return 0<=x && x<N && 0<=y && y<M && map[x][y]==0; }

void dfs(int x,int y){
    char tmp[30];
    sprintf(tmp,"(%d,%d)",x,y);
    top++; strcpy(stack[top],tmp);

    if(x == x2 && y == y2){
        cnt++;

        for(int i=0;i<=top;++i) {
            printf("%s",stack[i]);
        }puts("");

        stack[top--];
        return;
    }
    if(isAble(x+1, y)) {
        map[x+1][y] = 1;
        dfs(x+1, y);
        map[x+1][y] = 0;
    }
    if(isAble(x-1, y)){
        map[x-1][y] = 1;
        dfs(x-1, y);
        map[x-1][y] = 0;
    }
    if(isAble(x, y+1)){
        map[x][y+1] = 1;
        dfs(x, y+1);
        map[x][y+1] = 0;
    }
    if(isAble(x, y-1)){
        map[x][y-1] = 1;
        dfs(x, y-1);
        map[x][y-1] = 0;
    }

    stack[top--];
    return;
}

int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;++i) for(int j=0;j<M;++j)
        scanf("%d",&map[i][j]);
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    x1 = x1 - 1; x2 = x2 - 1;
    y1 = y1 - 1; y2 = y2 - 1;

    dfs(x1,y1);
    printf("%d",cnt);
    return 0 ;
}
这篇关于【练习回顾】dfs迷宫+路径打印的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!