[question 22] dungeons and Warriors (Beijing Institute of Technology / Beijing Institute of Technology / programming methods and practice / primary school)

Catalog

Description

Ideas

Code

My version

---

Description

The Dragon God felt bored and came to the dungeon , Here is a huge maze , There are some passable roads 、 Some impassable walls , There are also some monsters . Although the Dragon God can easily kill these monsters , But he thought it was too boring , He observed these monsters every k Seconds will disappear once （ for example k Equal to 3 when , Is the first 3 Commas Space 6 Commas Space 9 Commas Space Middle line ellipsis Second monsters disappear ）, Every second, the Dragon God can choose to walk up, down, left and right （ You can't stay where you are ）. The Dragon God wants to know that under the condition of avoiding all monsters , The shortest time required to reach the exit .

 Input Enter an integer in the first line T Space Left parenthesis 1 Less than T Less than 10 Right bracket , Represents the number of use case groups .   The first line of each set of use cases includes three integers n Commas Space m Space Left parenthesis 1 Less than n Commas Space m Less than 100 Right bracket and ,k Space Left parenthesis 1 Less than k Less than 50 Right bracket Respectively represent the number of lines in the dungeon maze 、 Number of columns 、 The disappearance interval of monsters .   Next n Lines represent mazes ,. Means a passable road ,# Represents a wall ,* It means monster ,S The starting point ,E It's for export .  

Output Output an integer , Indicates the shortest time for the Dragon God to get out of the dungeon maze , If the Dragon God can't get out of the maze, it will output -1.  

Source BITACM2018 The first round of points （ 3、 ... and ）- Problem J

Ideas

This question , Still bfs.

But it's different from the previous one .

You can go up. csdn search bfs Maze example , The most basic thing is to go through mazes ： A picture , Some walls , A starting point , A destination , Shortest path . The simplicity of this problem is that the maze itself is already a graph , So you just need to bfs that will do

At present, I have seen three variants of this maze ：

1. 21 This kind of question , I didn't give you a picture , Need to use map<int,vector<int>> To construct
2. 22 This kind of question , Given the ready-made map , But there is something strange , And it's not the shortest path , But the shortest time
3. There is another kind. , I want you to output the shortest path

The general idea of this question is not difficult , Namely Go through the maze , Regardless of time , set csdn Just use the template . 

The key is to understand why we need to open three-dimensional vis Array , Suppose my third dimension keeps updating , So no repetition will trigger the accessed tag , Until I passed a k cycle , It may trigger .

In fact, in theory, if you don't consider time, you don't need to open vis Of , Because under the action of monsters , We can go back （ At this time, it is no longer the maze problem of the shortest number of steps ）
The reason to open vis, In order to reduce unnecessary turning back , But there is a new problem ： How big is the third dimension ？
In order to solve the problem of unclear upper limit , I used % To limit the scope of , Save a space
% The rationality of ： In time time And time time+k Accessing the same location is completely equivalent ！
However time and time+k The weirdness of these two time points is exactly the same ,
in other words , In cycle , Instead, there is no strange influence , In other words, it is completely meaningless to take this step , So skip

Code

The original title is ,J

BITACM2018 The first round of points （ 3、 ... and ） Answer key _ There will always be oases swaying in the desert -CSDN Blog A. Very good dp The author ： zhber AC/TOT： 1/50 Answer key ： because V&quot; role=&quot;presentation&quot; style=&quot;position: relative;&quot;&gt;VVV It's too big , So make a backpack dp&quot; role=&quot;presentation&quot; style=&quot;position: relative;&ahttps://blog.csdn.net/dragon60066/article/details/79212465

My version

#include<cstdio>
#include<cstring>
#include<queue>
#define SIZE 101
const int dir[2][4] = { {1,0,0,-1},
						{0,1,-1,0} };
char maze[SIZE][SIZE];
bool vis[SIZE][SIZE][51];
struct point {
	int x;
	int y;
	int time;
	//point(int tx, int ty, int ttime)// Define a constructor for quick entry 
	//{
	//	x = tx;
	//	y = ty;
	//	time = ttime;
	//}
};
int main(void)
{
	freopen("input.txt", "r", stdin);
	int T;
	scanf("%d", &T);
	while (T--)
	{
		// Operate on each map 
		// initialization 
		point start, now, next, end;
		int n, m, k, ch;
		int ans = -1;
		std::queue <point> q;
		memset(vis, false, sizeof(vis));
		// Read in the picture 
		scanf("%d %d %d\n", &n, &m, &k);// Pay attention to absorbing line breaks 
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= m; j++)
			{
				ch = getchar();
				maze[i][j] = ch;
				if (ch == 'S')// Record the starting point 
				{
					start.x = i;
					start.y = j;
					start.time = 0;
				}
				if (ch == 'E')
				{
					end.x = i;
					end.y = j;
				}
			}
			getchar();// Every line has a newline 
		}
		//bfs
		q.push(start);
		vis[start.x][start.y][start.time % k] = true;
		while (!q.empty())
		{
			// Take out 
			now = q.front();
			q.pop();
			if (now.x == end.x && now.y == end.y)
			{
				ans = now.time;
				break;
			}
			// Put it in the next step 
			for (int i = 0; i < 4; i++)
			{
				next.x = now.x + dir[0][i];
				next.y = now.y + dir[1][i];
				next.time = now.time + 1;
				// Pay attention to the boundaries , wall , Repeat the visit , blame 
				if (next.x<1 || next.x>n || next.y > m || next.y < 1
					|| maze[next.x][next.y] == '#'
					|| vis[next.x][next.y][next.time % k]
					|| (maze[next.x][next.y] == '*' && next.time % k != 0))// This piece is written for readability ！=0, In fact, it's OK not to write 
				{
					continue;
				}
				q.push(next);
				vis[next.x][next.y][next.time % k] = true;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}