变换的迷宫

题面

你身处一个 r*s 的迷宫中，当前位置用 S 表示，迷宫的出口用 E 表示。迷宫中有一些石头，用 # 表示，还有一些可以随意走动的区域，用 . 表示。初始时间为 0 时，你站在地图中标记为 S 的位置上。你每移动一步（向上、下、左、右方向移动）会花费一个单位时间。你必须一直保持移动，不能停留在原地不走。当前时间是 K 的倍数时，迷宫中的石头就会消失，此时你可以走到这些位置上。再其余的时间中，你不能走到石头所在的位置。求你从初始位置走到迷宫出口最少需要花费多少个单位时间。如果无法走到出口，则输出 Oop!。

样例输入

1
6 6 2
...S..
...#..
.#....
...#..
...#..
..#E#.

样例输出

7

思路

深搜（代码少）

在 dfs 函数中，通过在循环中添加条件判断来减少不必要的递归调用，从而提高程序效率。在进入递归之前，会先判断是否满足以下条件：

当前位置超出迷宫边界或已被访问过；
当前时间已经超过了最短时间；
当前位置是墙壁 # 且时间不是 k 的倍数。
如果上述条件中的任何一个成立，则跳过该方向的递归调用。

在主函数中，使用 memset 函数将整个迷宫数组 s 初始化为 #，而不是只对部分数组进行初始化。这确保了没有输入的位置都被视为墙壁。

AC代码

#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<cstring>
#include<queue>
#include<unordered_map>
#include<map>

using namespace std;

const int N = 110;

char s[N][N];
bool st[N][N];
int ans;
int xs, ys, xe, ye;
int row, col, k;
int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };

void dfs(int x, int y, int time)
{
	if (x == xe && y == ye)
	{
		ans = time;
		return;
	}
	int xx = 0, yy = 0;
	for (int i = 0; i <= 3; i++)
	{
		int xx = x + dx[i], yy = y + dy[i];
        if(!(x <= 0 || y <= 0 || x > row || y > col || st[xx][yy])&&!(time+1 >= ans)&&!(s[xx][yy] == '#' && (time+1) % k != 0))
        {
		st[xx][yy] = true;

		dfs(xx, yy, time + 1);

		st[xx][yy] = false;
        }
				
	}

}

int main()
{
	int t;
	cin >> t;

	while (t--)
	{
		cin >> row >> col >> k;

		ans = 0x3f3f3f3f;
		memset(s, '#', sizeof s);

		for (int i = 1; i <= row; i++)
			for (int j = 1; j <= col; j++)
			{
				cin >> s[i][j];
				if (s[i][j] == 'S')xs = i, ys = j;
				if (s[i][j] == 'E')xe = i, ye = j;
			}


		dfs(xs, ys, 0);
		
		if (ans == 0x3f3f3f3f)cout << "Oop!" << endl;
		else  cout<<ans<<"\n";

		

	}

	return 0;
}