P1825

简单的题意

就是一个有传送门的迷宫问题（我一开始以为是只有1个传送门，然后我就凉了）.

大体思路

先把传送门先存起来，然后跑一下\(BFS\)。

然后，就做完了.

代码鸭

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <iomanip>

#include <vector>

#define A 305

using namespace std;

int ans, n, m, map[A][A], lu[400010][4];

int u[5] = {0, 0, 0, -1, 1}, v[5] = {0, -1, 1, 0, 0};

int dx, dy, sx, sy;

struct node {

	int x, y;

	bool s;

} w1[27], w2[27];

void bfs() {

	int head = 0, tail = 1;

	lu[tail][1] = sx, lu[tail][2] = sy, lu[tail][3] = 1;

	map[sx][sy] = 1;

	while(head < tail) {

		head++;

		for(int i = 1; i <= 4; i++) {

			int x = lu[head][1] + u[i], y = lu[head][2] + v[i];

			//if(w1.x == x && w1.y == y) x = w2.x, y = w2.y;

			//if(w2.x == x && w2.y == y) x = w1.x, y = w1.y;

			for(int i = 1; i <= 26; i++)

				if(x == w1[i].x && y == w1[i].y) {

					x = w2[i].x, y = w2[i].y;

					break;

				} else if(x == w2[i].x && y == w2[i].y) {

					x = w1[i].x, y = w1[i].y;

					break;

				}

			if(x >= 1 && x <= n && y >= 1 && y <= m && map[x][y] == 0) {

				tail++;

				map[x][y] = 1;

				lu[tail][1] = x, lu[tail][2] = y, lu[tail][3] = lu[head][3] + 1;

				if(x == dx && y == dy) {

					ans = lu[tail][3];

					head = tail;

					break;

				}

			}

		}

	}

}

int main() {

	char s;

	scanf("%d%d",&n, &m);

	for (int i = 1; i <= n; i++)

		for (int j = 1; j <= m; j++) {

			cin>>s;

			if (s == '=') dx = i, dy = j, map[i][j] = 0;

			if (s == '@') sx = i, sy = j, map[i][j] = 0;

			if (s == '#') map[i][j] = 1;

			if (s == '.') map[i][j] = 0;

			if (s >= 'A' && s <= 'Z') {

				map[i][j] = 0;

				if (w1[s - 'A' + 1].s == 0) w1[s - 'A' + 1].s = 1, w1[s - 'A' + 1].x = i, w1[s - 'A' + 1].y = j;

				else w2[s - 'A' + 1].s = 1, w2[s - 'A' + 1].x = i, w2[s - 'A' + 1].y = j;

			}

		}

	bfs();

	cout<<ans - 1;

}

巴特西

洛谷 P1825 【[USACO11OPEN]玉米田迷宫Corn Maze】

P1825

简单的题意

大体思路

代码鸭

最新文章

热门文章