求助dfs!!
  • 板块P1141 01迷宫
  • 楼主Epi4any
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/2/26 10:04
  • 上次更新2023/10/28 07:44:24
查看原帖
求助dfs!!
374769
Epi4any楼主2022/2/26 10:04

谁来帮忙看看 样例过了

#include<iostream>
#define INF 1000000
#define N 1005
using namespace std;

const int dx[5] = {0, 0, -1, 0, 1};
const int dy[5] = {0, -1, 0, 1, 0};

//  2
//1 0 3
//  4

int n, m, ans=-INF;
bool mp[N][N], vis[N][N];

inline bool inbound(int x, int y) {
	return x >= 1 && x <= n && y >= 1 && y <= n;
}

void dfs(int x, int y, int step) {
	bool f = false;
	for (int i = 1; i <= 4; i++) {
		if (inbound(x + dx[i], y + dy[i]) && !vis[x + dx[i]][y + dy[i]] 
		                       && mp[x + dx[i]][y + dy[i]] != mp[x][y]) {
			f = true;
			vis[x + dx[i]][y + dy[i]] = true;
			dfs(x + dx[i], y + dy[i], step + 1);
			vis[x + dx[i]][y + dy[i]] = false;
		}
	}
	if (!f) {
		ans=max(ans,step);
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		char s[N];
		cin >> s;
		for (int j = 0; j < n; j++) {
			mp[i][j + 1] = s[j] - '0';
		}
	}

	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		vis[x][y]=true;
		dfs(x, y, 1);
		vis[x][y]=false;
		cout<<ans<<endl;
	}
	return 0;
}
2022/2/26 10:04
加载中...