P1825 Corn Maze S

无脑深搜，然后卡死在了37pts。

#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;

struct coord {
	int x, y;
};

int walk[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int n, m, sx, sy, ans = 0x7fffffff;
char map[301][301]; 
coord tpGate[100][2];
int cnt[100];
bool vis[301][301];
bool use_gate[100];

bool is_tp(char ch)
{
	return ch >= 'A' && ch <= 'Z'; 
}

void findTpEnd(int ch, int x, int y,int& dx, int& dy)
{
	if (tpGate[ch][0].x == x && tpGate[ch][0].y == y)
	{
		dx = tpGate[ch][1].x, dy = tpGate[ch][1].y;
		return ;
	} 
	else 
	{
		dx = tpGate[ch][0].x, dy = tpGate[ch][0].y; 
		return ;
	}
}

void dfs(int step, int x, int y)
{
	if (step > ans)
	{
		return ;
	}
	if (map[x][y] == '=')
	{
		ans = min(ans, step);
		return;
	}
	int temp = (int)map[x][y];
	if (is_tp(map[x][y]))
	{
		int tx, ty;
		findTpEnd(temp, x, y, tx, ty); 
		if (!vis[tx][ty])
		{
			vis[tx][ty] = true;
			dfs(step, tx, ty);
			vis[tx][ty] = false;
			return ;
		}
	}
	for (int i = 0; i < 4; i++)
	{
		int dx = x + walk[i][0], dy = y + walk[i][1];
		if (dx < 1 || dx > n || dy < 1 || dy > m || vis[dx][dy] || map[dx][dy] == '#') continue;
		vis[dx][dy] = true;
		dfs(step + 1, dx, dy);
		vis[dx][dy] = false;
	}
}

int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> map[i][j];
			if (is_tp(map[i][j]))
			{
				int temp = map[i][j];
				tpGate[temp][cnt[temp]].x = i;
				tpGate[temp][cnt[temp]].y = j;
				cnt[temp]++;
 			}
 			if (map[i][j] == '@')
 			{
 				sx = i, sy = j;	
			}
		}
	}
	dfs(0, sx, sy);
	printf("%d", ans);
	return 0;
}

找到传送门标记问题

T了几个点，WA了几个点，想到说传送门是可能再次使用的，不能用vis数组来判断，但细想下来，主要是传过去之后不能立马传回来，但是可能走一段之后再回到这个传送门，所以传送到的传送门是不能标记的。基于这个思想，我选择特判进入dfs时是否是传送门，是的话说明刚传到不能标记，否则就标记

改完后没有正确性问题了，\(55pts\)，T了一半。

#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;

struct coord {
	int x, y;
};

int walk[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int n, m, sx, sy, ans = 0x7fffffff;
char map[301][301]; 
coord tpGate[100][2];
int cnt[100];
bool vis[301][301];
bool use_gate[100];

bool is_tp(char ch)
{
	return ch >= 'A' && ch <= 'Z'; 
}

void findTpEnd(int ch, int x, int y,int& dx, int& dy)
{
	if (tpGate[ch][0].x == x && tpGate[ch][0].y == y)
	{
		dx = tpGate[ch][1].x, dy = tpGate[ch][1].y;
		return ;
	} 
	else 
	{
		dx = tpGate[ch][0].x, dy = tpGate[ch][0].y; 
		return ;
	}
}

void dfs(int step, int x, int y)
{
	if (!is_tp(map[x][y]))
	{
		vis[x][y] = true;
	}
	if (step > ans)
	{
		return ;
	}
	if (map[x][y] == '=')
	{
		ans = min(ans, step);
		return;
	}
	
	for (int i = 0; i < 4; i++)
	{
		int dx = x + walk[i][0], dy = y + walk[i][1];
		if (dx < 1 || dx > n || dy < 1 || dy > m || vis[dx][dy] || map[dx][dy] == '#') continue;
		if (is_tp(map[dx][dy]))
		{
			int tx, ty;
			int temp = (int)map[dx][dy];
			findTpEnd(temp, dx, dy, tx, ty); 
			if (cnt[temp] == 2) 
			{
				vis[dx][dy] = true;
				dfs(step + 1, tx, ty); 
				vis[dx][dy] = false;
			} else {
				dfs(step + 1, dx, dy);
				vis[dx][dy] = false;
			}
		} else {
			dfs(step + 1, dx, dy);
			vis[dx][dy] = false;
		}
	}
}

int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> map[i][j];
			if (is_tp(map[i][j]))
			{
				int temp = map[i][j];
				tpGate[temp][cnt[temp]].x = i;
				tpGate[temp][cnt[temp]].y = j;
				cnt[temp]++;
 			}
 			if (map[i][j] == '@')
 			{
 				sx = i, sy = j;	
			}
		}
	}
	dfs(0, sx, sy);
	printf("%d", ans);
	return 0;
}

使用算法错误

想想怎么记忆化搜索或者剪枝优化吧。

然而几乎是毫无思路了，因为传送门的存在，我想不到很优秀的记忆化状态，剪枝大概率也是玄学。

点开这道题标签，猛然看见BFS和最短路。

这才意识到这题用BFS更好，毕竟BFS的特性让他在求最短路径的时候有远超DFS的优势。

于是又开始打BFS。

因为觉得大同小异，所以几乎是直接把DFS代码复制了过去，但是却又T又M。

\(67pts\) code

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>

using namespace std;

struct coord {
	int x, y;
};

struct status {
	int x, y, step;
};

int walk[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int n, m, sx, sy, ans = 0x7fffffff;
char map[301][301]; 
coord tpGate[100][2];
queue<status> Q;
int cnt[100];
int ansArr[301][301];
bool vis[301][301];

bool is_tp(char ch)
{
	return ch >= 'A' && ch <= 'Z'; 
}

void findTpEnd(int ch, int x, int y,int& dx, int& dy)
{
	if (tpGate[ch][0].x == x && tpGate[ch][0].y == y)
	{
		dx = tpGate[ch][1].x, dy = tpGate[ch][1].y;
		return ;
	} 
	else 
	{
		dx = tpGate[ch][0].x, dy = tpGate[ch][0].y; 
		return ;
	}
}

void BFS()
{
	Q.push({sx, sy, 0});
	while(!Q.empty())
	{
		status node = Q.front();
		Q.pop();
		int x = node.x, y = node.y, step = node.step;
		if (!is_tp(map[x][y]))
		{
			vis[x][y] = true;
		}
		if (map[x][y] == '=')
		{
			ans = step;
			return ;
		}
		for (int i = 0; i < 4; i++)
		{
			int dx = x + walk[i][0], dy = y + walk[i][1];
			if (dx < 1 || dx > n || dy < 1 || dy > m || vis[dx][dy] || map[dx][dy] == '#') continue;
			if (is_tp(map[dx][dy]))
			{
				int tx, ty;
				int temp = (int)map[dx][dy];
				findTpEnd(temp, dx, dy, tx, ty); 
				if (cnt[temp] == 2) 
				{
					vis[dx][dy] = true;
					Q.push({tx, ty, step + 1});
					vis[dx][dy] = false;
				} else {
					Q.push({dx, dy, step + 1});
					vis[dx][dy] = false;
				}
			} else {
				Q.push({dx, dy, step + 1});
				vis[dx][dy] = false;
			}
		}
	}
	
}

int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> map[i][j];
			if (is_tp(map[i][j]))
			{
				int temp = map[i][j];
				tpGate[temp][cnt[temp]].x = i;
				tpGate[temp][cnt[temp]].y = j;
				cnt[temp]++;
 			}
 			if (map[i][j] == '@')
 			{
 				sx = i, sy = j;	
			}
		}
	}
	BFS();
	printf("%d", ans);
	return 0;
}

稍微用点脑子，明显的两个问题

• 回溯语句没删，合着BFS也回溯是吧
• 递归的思想直接照搬，剪枝那些也得删。

处理完之后TLE，没办法，不能偷懒，重写BFS。

这次学聪明了，不在for枚举坐标的时候特判传送门，而是枚举前直接特判传送门，如果是的话直接把当前操作的队列点改为传送后的队列点，一下省了一堆特判。

搞了三个半小时，终于AC。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>

using namespace std;

struct coord {
	int x, y;
};

struct status {
	int x, y, step;
};

int walk[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int n, m, sx, sy, ans = 0x7fffffff;
char map[301][301]; 
coord tpGate[130][2];
queue<status> Q;
int cnt[130];
bool vis[301][301];

bool is_tp(char ch)
{
	return ch >= 'A' && ch <= 'Z'; 
}

void findTpEnd(int ch, int x, int y,int& dx, int& dy)
{
	if (tpGate[ch][0].x == x && tpGate[ch][0].y == y)
	{
		dx = tpGate[ch][1].x, dy = tpGate[ch][1].y;
		return ;
	} 
	else 
	{
		dx = tpGate[ch][0].x, dy = tpGate[ch][0].y; 
		return ;
	}
}

void BFS()
{
	Q.push({sx, sy, 0});
	while(!Q.empty())
	{
		status node = Q.front();
		Q.pop();
		int x = node.x, y = node.y, step = node.step;
		if (map[x][y] == '=')
		{
			ans = step;
			return ;
		}
		if (is_tp(map[x][y]))
		{
			findTpEnd(map[x][y], x, y, x, y);
		}
		for (int i = 0; i < 4; i++)
		{
			int dx = x + walk[i][0], dy = y + walk[i][1];
			if (dx < 1 || dx > n || dy < 1 || dy > m || vis[dx][dy] || map[dx][dy] == '#') continue;
			vis[dx][dy] = true;
			Q.push({dx, dy, step + 1}); 
		}
	}
	
}

int main()
{
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> map[i][j];
			if (is_tp(map[i][j]))
			{
				int temp = map[i][j];
				tpGate[temp][cnt[temp]].x = i;
				tpGate[temp][cnt[temp]].y = j;
				cnt[temp]++;
 			}
 			if (map[i][j] == '@')
 			{
 				sx = i, sy = j;	
			}
		}
	}
	BFS();
	printf("%d", ans);
	return 0;
}

本栏目推荐文章
• HDU #6664. Andy and Maze 题解--zhengjun
• C语言中这几种数组，弄明白了吗？int(*pai[2])[5]，int *aapi[2][2]， int **p[2]， int *numT[5]， int(*num2)[5]
• 聊聊ChatGLM中P-tuning v2的应用
• P1164-小A点菜
• Programming Abstractions in C阅读笔记：p242-p245
• P1990-覆盖墙壁
• P7830 [CCO2021] Through Another Maze Darkly
• P9194 [USACO23OPEN] Triples of Cows P 题解
• P7816/CF1610F「Stoi2029」以父之名 题解
• *p++、(*p)++、*++p、++*p的区别

P1825 1825 Corn Mazep1825 corn maze usaco open corn maze p1825 1825 1825c 1825d 1825a 1825 div cf 题解1825d cf d1 1801 1825 cf