35玄关,蒟蒻求调
  • 板块P1238 走迷宫
  • 楼主isop
  • 当前回复7
  • 已保存回复8
  • 发布时间2024/7/25 19:45
  • 上次更新2024/7/25 20:39:05
查看原帖
35玄关,蒟蒻求调
1071516
isop楼主2024/7/25 19:45
#include<bits/stdc++.h>
using namespace std;

int m, n, sx, sy, fx, fy, a, b, tem=1; //tem路径节点数
int g[17][17];
int dx[4] = {-1, 0, 1, 0}; //方向数组
int dy[4] = {0, 1, 0, -1};
bool flag = false;
vector<pair<int, int>>p; //存路径

inline void print(int w) { //输出路径
	for (int i = 0; i < w - 1; i++) {
		cout << "(" << get<0>(p[i]) << "," << get<1>(p[i]) << ")" << "->";
	}
	cout << "(" << get<0>(p[w - 1]) << "," << get<1>(p[w - 1]) << ")" << endl;
}

inline int read() {
	int a = 0, f = 1;
	char c = getchar();
	while (!isdigit(c)) {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (isdigit(c)) {
		a = (a << 3) + (a << 1) + (c^'0');
		c = getchar();
	}
	return a * f;
}

inline void dfs(int x, int y) {
	if (x == fx && y == fy) {
		flag = true;
		print(tem);
		return;
	}
	for (int i = 0; i < 4; i++) {
		int a = x + dx[i], b = y + dy[i];
		if (a < 1 || a > m || b < 1 || b > n) continue; //出界
		if (!g[a][b]) continue; //访问过
		g[a][b] = 0;
		tem++;
		p.push_back({a, b});
		dfs(a, b);
		g[a][b] = 1; //回溯
		p.pop_back();
		tem--;
	}
}

int main() {
	m = read(), n = read();
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			g[i][j] = read();
		}
	}
	sx = read(), sy = read(), fx = read(), fy = read();
	g[sx][sy] = 0;
	p.push_back({sx, sy});
	dfs(sx, sy);
	if (flag == false) printf("%d", -1);
}
2024/7/25 19:45
加载中...