poj 3984 迷宫问题 —— 典型搜索--DFS递归

系统管理员 2023-01-16 06:56 133阅读 0赞

四个方向，每次选择一个方向走，不通时走下一个方向，如果四个方向都不能走时，则退一格。依题意，可用DFS递归实现。

#include<stdio.h>
    #include<string.h>
    int n,m,i,j,k,flag,count;
    int data[5][5],vis[5][5]; 
    int dir[4][2]={ { 1,0},{ 0,1},{ -1,0},{ 0,-1}};
    struct Path
    { 
      int a,b;
    }path[10][10];
    void dfs(int x,int y)
    { 
    	int i,xx,yy;
    	if(x==4&&y==4){ 
    	flag=1;
    	return;
    	}
      for(i=0;i<4;i++)
      { 
        xx = x+dir[i][0];
    	yy = y+dir[i][1];
    	if(vis[xx][yy]==0&&data[xx][yy]==0&&xx>=0&&xx<5&&yy>=0&&yy<5)
    	{ 
    		vis[xx][yy] = 1;
    		path[xx][yy].a=x;
    		path[xx][yy].b=y;
    	    dfs(xx,yy);
    
    		if(flag) return;
    
    		path[xx][yy].a=-1;
    		path[xx][yy].b=-1;
    		vis[xx][yy]=0;
    	}
      }
    }
    int main()  // 迷宫问题
    { 
     for(i=0;i<5;i++)
      for(j=0;j<5;j++)
    	  scanf("%d",&data[i][j]);
      memset(vis,0,sizeof(vis));
      memset(path,-1,sizeof(path));
      flag=0;
      dfs(0,0);
      for(i=0;i<5;i++)
        for(j=0;j<5;j++)
    		if(path[i][j].a!=-1)
    		printf("(%d, %d)\n",path[i][j].a,path[i][j].b);
    	printf("(4, 4)\n");
      return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，133人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ3984 迷宫问题（BFS）

\include<cstdio> \include<cstring> \include<queue> \include<vector> using namesp

爱被打了一巴掌/ 2024年02月17日 18:25/ 0 赞/ 29 阅读

相关 POJ - 3984 迷宫问题

POJ - 3984 迷宫问题题目链接：[https://vjudge.net/problem/POJ-3984][https_vjudge.net_problem_

柔光的暖阳◎/ 2023年08月17日 15:40/ 0 赞/ 123 阅读

相关 poj 3984 迷宫问题 —— 典型搜索--DFS递归

四个方向，每次选择一个方向走，不通时走下一个方向，如果四个方向都不能走时，则退一格。依题意，可用DFS递归实现。 include<stdio.h> inclu

系统管理员/ 2023年01月16日 06:56/ 0 赞/ 134 阅读

相关 POJ 3984 迷宫问题

迷宫问题定义一个二维数组： int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0

你的名字/ 2022年10月02日 14:57/ 0 赞/ 145 阅读

相关 poj 3984 迷宫问题【BFS && DFS】【简单】

迷宫问题 <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

布满荆棘的人生/ 2022年08月10日 09:16/ 0 赞/ 211 阅读

相关 poj 3984 迷宫问题【dfs】

迷宫问题 Sample Input 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0

￡神魔★判官ぃ/ 2022年08月09日 01:48/ 0 赞/ 179 阅读

相关 POJ 3984 迷宫问题

> 迷宫问题 > Time Limit: 1000MS Memory Limit: 65536K > Total Submissions: 20612 Accepted

待我称王封你为后i/ 2022年06月18日 09:48/ 0 赞/ 133 阅读

相关 J - 迷宫问题 POJ - 3984

Think: 1BFS+记录路径 J - 迷宫问题 POJ - 3984 定义一个二维数组： int maze[5][5] = {

缺乏、安全感/ 2022年06月15日 01:57/ 0 赞/ 177 阅读

相关 POJ 3984 迷宫问题 —————— BFS

Language:Default 迷宫问题 <table> <tbody> <tr> <td><b>Time Limit:</b> 1000MS</td>

- 日理万妓/ 2022年05月12日 02:34/ 0 赞/ 237 阅读

相关 POJ 3984 迷宫问题（bfs）

嗯... 题目链接：[http://poj.org/problem?id=3984][http_poj.org_problem_id_3984] 这道

深藏阁楼爱情的钟/ 2021年10月29日 21:12/ 0 赞/ 390 阅读