代码

P1238 走迷宫(水水的DFS)

[successbox title="P1238 走迷宫"]题目描述

有一个m*n格的迷宫(表示有m行、n列),其中有可走的也有不可走的,如果用1表示可以走,0表示不可以走,文件读入这m*n个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的,分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路,要求所走的路中没有重复的点,走时只能是上下左右四个方向。如果一条路都不可行,则输出相应信息(用-l表示无路)。

https://www.luogu.org/problem/show?pid=1238

[/successbox]

题解:
水水的DFS...注意记录和搜索方向就行了,浪费我AC率...

#include<cstdio>
#include<iostream>
#include<cstring>
#define MAXN 16
using namespace std;
int n, m;
int g[MAXN][MAXN];
bool vis[MAXN][MAXN];
int	r[MAXN * MAXN][2];
int ex, ey, ix, iy;
bool flag = 0;
void dfs(int x, int y, int st){
	if (x < 1 || x > n || y < 1 || y > m || g[x][y] == 0) return;
	if (x == 2 && y == 5){
	}
	vis[x][y] = 1;
	r[st][0] = x, r[st][1] = y;
	if (x == ex && y == ey){
		for (int i = 0; i < st + 1; i++){
			printf("(%d,%d)", r[i][0], r[i][1]);
			if (i != st) printf("->");
			flag = 1;
		}
		printf("\n");
		return;
	}

	if (!vis[x][y - 1]) dfs(x, y - 1, st + 1), vis[x][y - 1] = 0;
	if (!vis[x - 1][y]) dfs(x - 1, y, st + 1), vis[x - 1][y] = 0;
	if (!vis[x][y + 1]) dfs(x, y + 1, st + 1), vis[x][y + 1] = 0;
	if (!vis[x + 1][y]) dfs(x + 1, y, st + 1), vis[x + 1][y] = 0;

}

int main(){
	memset(vis, 0, sizeof(vis));
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++){
			scanf("%d", &g[i][j]);
		}
	scanf("%d%d%d%d", &ix, &iy, &ex, &ey);
	dfs(ix, iy, 0);
	if (!flag) printf("-1");
	return 0;
}

b-a
我还没有学会写个人说明!
查看“b-a”的所有文章 →

Leave a Reply

Your email address will not be published. Required fields are marked *

相关推荐