求助卡常,不吸氧82pts
查看原帖
求助卡常,不吸氧82pts
292300
Kobe303楼主2021/8/15 20:20
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define reg register 
#define il inline
const int N = 505;
int n, m;
char mp[N][N];
bool vis[N][N];
int dis[N][N];
vector<pair<pair<int, int>, int> > p[N][N];
deque<pair<int, int> > q;
il void add(int x1, int y1, int x2, int y2, int z)
{
	p[x1][y1].push_back(make_pair(make_pair(x2, y2), z));
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) scanf("%s", mp[i] + 1);
	if ((n + m) & 1) {
		printf("NO SOLUTION");
		return 0;
	}
	for (reg int i = 1; i <= n; ++i)
		for (reg int j = 1; j <= m; ++j)
			if (mp[i][j] == '/') {
				add(i - 1, j - 1, i, j, 1);
				add(i, j, i - 1, j - 1, 1);
				add(i - 1, j, i, j - 1, 0);
				add(i, j - 1, i - 1, j, 0);
			} else {
				add(i - 1, j - 1, i, j, 0);
				add(i, j, i - 1, j - 1, 0);
				add(i - 1, j, i, j - 1, 1);
				add(i, j - 1, i - 1, j, 1);
			}
	for (reg int i = 0; i <= n; ++i)
		for (reg int j = 0; j <= m; ++j)
			dis[i][j] = 0x3f3f3f3f;
	dis[0][0] = 0;
	q.push_back(make_pair(0, 0));
	while (!q.empty()) {
		int x = q.front().first, y = q.front().second;
		q.pop_front();
		vis[x][y] = 1;
		if (x == n && y == m) {
			printf("%d", dis[n][m]);
			break;
		}
		for (reg int i = 0; i < p[x][y].size(); ++i) {
			int nx = p[x][y][i].first.first;
			int ny = p[x][y][i].first.second;
			int z = p[x][y][i].second;
			if (vis[nx][ny]) continue;
			if (z) {
				if (dis[nx][ny] > dis[x][y] + 1) {
					dis[nx][ny] = dis[x][y] + 1;
					q.push_back(make_pair(nx, ny));
				}
			} else {
				if (dis[nx][ny] > dis[x][y]) {
					dis[nx][ny] = dis[x][y];
					q.push_front(make_pair(nx, ny));
				}
			}
		}
	} 
	return 0;
}

2021/8/15 20:20
加载中...