16954 움직이는 미로 탈출 C++ DFS deque

캐릭터는 상하좌우대각선, 제자리로 움직일 수 있다.

벽은 계속 아래로 내려가다가 사라진다.

 

벽의 크기는 8이므로 8번 벽이 내려가는동안 캐릭터가 살아있다면 목적지에 100% 도착이 가능하다.

 

여기서 곤란한것은 맵을 벽으로 내리고, DFS돌리고난후 맵을 원래대로 복구해야된다는 것인데,

벽은 계속 맨아래에 있는것이 전부 사라지므로, 위로 빈공간을 생성시키면 된다.

 

양쪽으로 삽입이 가능한 deque를 사용하면 바로 적용할 수 있다.

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <memory.h>
#include <deque>
using namespace std;

int n, m, k;
int dx[8] = { 0,0,1,-1 ,1,1,-1,-1};
int dy[8] = { 1,-1,0,0 ,-1,1,-1,1};
deque<string> vmap;
int ans = 0;

void dfs(int y, int x, int cnt)
{
	if (cnt >= 8)
	{
		ans = 1;
		return;
	}
	if (y == 0 && x == 7)
	{
		ans = 1;
		return;
	}
	string savestr = vmap[7];
	string inputstr = "........";

	if (cnt >= 1)
	{
		vmap.pop_back();
		vmap.push_front(inputstr);
	}
	if (vmap[y][x] == '#')
	{
		if (cnt >= 1)
		{
			vmap.pop_front();
			vmap.push_back(savestr);
		}
		return;
	}
		
	for (int i = 0; i < 8; ++i)
	{
		int cy = y + dy[i];
		int cx = x + dx[i];
		if (cx < 0 || cx >= 8 || cy < 0 || cy >= 8)
			continue;
		if (vmap[cy][cx] == '#')
			continue;
		dfs(cy, cx, cnt + 1);
	}
	dfs(y, x, cnt + 1);

	if (cnt >= 1)
	{
		vmap.pop_front();
		vmap.push_back(savestr);
	}
		
}


int main()
{
	for (int i = 0; i < 8; ++i)
	{
		string str;
		cin >> str;
		vmap.push_back(str);
	}

	dfs(7,0, 0);
	cout << ans;
	return 0;

}