Tutorial For: 377-A Maze

Revision en1, by cn.Hwongfish, 2020-09-06 16:13:55
  • Hello!
  • I really love this problem very classic and interesting.
  • (JUST novice coder)
  • 377-A Maze
  • My algorithm has these points need to be careful:
    • 1.If we want to let the maze still connected we can just delete the unit that doesn't have their son
    • 2.dfs's end is the unit that doesn't have their son
    • 3.Put the "X" onto it!
#include<iostream>
using namespace std;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int n = 0, m = 0, k = 0;
bool st[501][501] = { 0 };
char map[501][501] = { 0 };
bool dfs(int x, int y) {
	st[x][y] = 1;
	for (int i = 0; i < 4; i++)
	{
		int x1 = x + dx[i];
		int y1 = y + dy[i];
		if (!st[x1][y1] && map[x1][y1] == '.')
		{
			dfs(x1, y1);
		}
	}
	if (k > 0) {
		map[x][y] = 'X';
		k--;
	}
	return false;
}
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 0; i < n; ++i)
		scanf("%s",map[i]);
	int ti = 0, tj = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			if (map[i][j] == '.')
			{
				dfs(i, j);
				for (int i = 0; i < n; ++i) {
					for (int j = 0; j < m; ++j)
						printf("%c", map[i][j]);
					printf("\n");
				}
				return 0;
			}
	}
	return 0;
}
Tags novice coder, #code

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English cn.Hwongfish 2020-09-06 16:13:55 1286 Initial revision (published)