P10486求解
  • 板块学术版
  • 楼主bear120618
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/18 16:26
  • 上次更新2024/5/18 17:06:16
查看原帖
P10486求解
1256697
bear120618楼主2024/5/18 16:26
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 507;
constexpr int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, 1, -1};
string cs = R"(\/\/)";
constexpr int ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1};
struct node {
	int x, y;
};
char g[N][N];
int n, m;
int dist[N][N];
bool st[N][N];
int bfs() {
	memset(dist, 0x3f, sizeof(dist));
	dist[0][0] = 0;
	deque<node> dq;
	dq.push_back({0, 0});
	while (!dq.empty()) {
		node t = dq.front();
		dq.pop_front();
		if (st[t.x][t.y]) continue;
		st[t.x][t.y] = true;
		for (int i = 0; i < 4; i++) {
			int xx = t.x + dx[i], yy = t.y + dy[i];
			if (xx < 0 || xx > n || yy < 0 || yy > m) continue;
			int ca = t.x + ix[i], cb = t.y + iy[i];
			int d = dist[t.x][t.y] + (g[ca][cb] != cs[i]);
			if (d < dist[xx][yy]) {
				dist[xx][yy] = d;
				if (g[ca][cb] != cs[i]) {
					dq.push_back({xx, yy});
				} else {
					dq.push_front({xx, yy});
				}
			}
		}
	}
	return dist[n][m];
}
int main() {
	int op;
	cin>>op;
	while(op--) {
		cin >> n >> m;
		for (int i = 0; i < n; i++) cin >> g[i];
		int t = bfs();
		if (t == 0x3f3f3f3f) {
			cout << "NO SOLUTION\n";
		} else {
			cout << t << "\n";
		}
	}
	return 0;
}

请各位大佬帮忙看看

2024/5/18 16:26
加载中...