ACM 训练日志记录 · 思考 · 成长 提交 / 修改记录
廖夏 / 题目列表训练档案
导出

P1825 [USACO11OPEN] Corn Maze S

来源:洛谷 ★ 1300

本题活力0.32按难度、完成结果与训练证据估算

算法如山行则将至

题目描述

[USACO11OPEN] Corn Maze S

题目描述

去年秋天,农夫约翰带着奶牛们参观了一个玉米迷宫。但这不是一个普通的玉米迷宫:它有几个重力驱动的传送滑梯,可以让奶牛瞬间从迷宫中的一个点传送到另一个点。滑梯是双向的:奶牛可以瞬间从滑梯的起点滑到终点,或者从终点滑到起点。如果奶牛踩到滑梯的任一端,她必须使用滑梯。

传送操作不能连续使用,即,传送一次之后,必须通过非传送方式移动至少一步才能再次进行传送。

玉米迷宫的外部完全由玉米包围,只有一个出口。

迷宫可以用一个 $N \times M$($2 \leq N \leq 300$;$2 \leq M \leq 300$)的网格表示。每个网格元素包含以下项目之一:

  • 玉米(玉米网格元素不可通行)
  • 草地(容易通过!)
  • 滑梯端点(会将奶牛传送到另一个端点)
  • 出口

奶牛只能从一个空间移动到相邻的下一个空间,前提是它们相邻且都不包含玉米。每个草地空间有四个潜在的邻居可以让奶牛到达。从一个草地空间移动到相邻空间需要 $1$ 个时间单位;从一个滑梯端点移动到另一个端点需要 $0$ 个时间单位。

填满玉米的空间用井号(#)表示。草地空间用英文句号(.)表示。滑梯端点对用相同的大写字母(A 到 Z)表示,并且没有两个不同的滑梯端点用相同的字母表示。出口用等号(=)表示。

贝茜迷路了。她知道自己在网格中的位置,并用「at」符号(@)标记了她当前的草地空间。她需要的最短时间是多少才能移动到出口空间?

输入格式

第一行:两个用空格隔开的整数 $N$ 和 $M$。

第 $2 \sim N+1$ 行:第 $i+1$ 行描述了迷宫中的第 $i$ 行的情况(共有 $M$ 个字符,每个字符之间没有空格)。

输出格式

一个整数,表示起点到出口所需的最短时间。

说明/提示

例如以下矩阵,$N=5,M=6$。

###=##
#.W.##
#.####
#.@W##
######

唯一的一个装置的结点用大写字母 $\tt{W}$ 表示。

最优方案为:先向右走到装置的结点,花费一个单位时间,再到装置的另一个结点上,花费 $0$ 个单位时间,然后再向右走一个,再向上走一个,到达出口处,总共花费了 $3$ 个单位时间。

(由 ChatGPT 4o 翻译)

代码

// 以下为DFS代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
const int MAXN = 305;
char mp[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dist[MAXN][MAXN];
int n, m, ans = 100000;
int sx, sy, endx, endy;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
struct Portal{
	int x1, y1;
	int x2, y2;
};
struct coord{
	int x, y;
	bool operator<(const coord& other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
};
map<char, Portal> _ptls;
map<coord, coord> ptls;
bool is_letter(int x, int y){
	return mp[x][y] >= 'A' && mp[x][y] <= 'Z';
}
void dfs(int x, int y, int cnt){
	if (dist[x][y] && cnt >= dist[x][y]) return;
	else dist[x][y] = cnt;
	// cout << x << " " << y << " " << mp[x][y] << endl;
//	if (mp[x][y] == '=') {ans = min(cnt, ans); return;}
	for (int k = 0; k < 4; k++){
		int nx = x + dx[k], ny = y + dy[k];
		// cout << nx << " " << ny << " " << mp[nx][ny] << endl;
		if (nx >= 1 && ny >= 1 && nx <= n && ny <= m
			&& mp[nx][ny] != '#' && mp[nx][ny] != '@'){
			// cout << nx << " " << ny << " " << mp[nx][ny] << endl;
			char nt = mp[nx][ny];
			if (nt == '.' && !vis[nx][ny]) {
				vis[nx][ny] = true;
				dfs(nx, ny, cnt + 1);
				vis[nx][ny] = false;
			}
			if (nt == '='){
				ans = min(ans, cnt + 1);
				continue;
			}
			if (is_letter(nx, ny)){
				coord p = ptls[{nx, ny}];
				if (vis[p.x][p.y]) continue;
				vis[p.x][p.y] = true;
				dfs(p.x, p.y, cnt + 1);
				vis[p.x][p.y] = false;
			}
		}
	}
}
int main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++){
			cin >> mp[i][j];
			if (mp[i][j] >= 'A' && mp[i][j] <= 'Z'){
				if (_ptls.find(mp[i][j]) == _ptls.end()) _ptls[mp[i][j]].x1 = i, _ptls[mp[i][j]].y1 = j;
				else _ptls[mp[i][j]].x2 = i, _ptls[mp[i][j]].y2 = j;
			}
			else if(mp[i][j] == '@')
				sx = i, sy = j;
		}
	for (auto pt : _ptls){
		coord p1, p2;
		p1.x = pt.second.x1, p1.y = pt.second.y1;
		p2.x = pt.second.x2, p2.y = pt.second.y2;
		ptls[p1] = p2;
		ptls[p2] = p1;
	}
	dfs(sx, sy, 0);
	cout << ans;
}


// 以下为BFS代码

void bfs(int sx, int sy) {
    queue<coord> q;
    q.push({sx, sy});
    vis[sx][sy] = true;
    dist[sx][sy] = 0;
    while (!q.empty()) {
        coord u = q.front();
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = u.x + dx[k];
            int ny = u.y + dy[k];
            if (nx < 1 || ny < 1 || nx > n || ny > m)
                continue;
            char nt = mp[nx][ny];
            if (nt == '#' || nt == '@')
                continue;
            if (nt == '=') {
                ans = dist[u.x][u.y] + 1;
                return;
            }
            coord p = {nx, ny};
            if (is_letter(nx, ny))
                p = ptls[p];
            if (vis[p.x][p.y])
                continue;
            vis[p.x][p.y] = true;
            dist[p.x][p.y] = dist[u.x][u.y] + 1;
            q.push(p);
        }
    }
}