꽤 빈번히 나오는 완전탐색류 라고 생각했지만 생각보다 조건이 까다로운 부분도 있어서 애를 좀 먹었다. 가장 밑에 안전지대 까지 가는 최소 경로를 구해야 하는 문제였지만 U 로표시되어있는 우산의 내구도를 신경 써주면서 가야했었다.
이 문제는 예전에 SK 코테에서 풀었던 캠프 문제와 유사하다고 생각했는데 뭔가 맞는거 같다. 원래는 visited 배열을 다차원으로 늘려서 BFS를 할 생각이였는데 너무 복잡해졌다. visited[a][b][우산][내구도] 이런식으로 진행 하게되면 아무리 BFS여도 너무나도 많은 상태를 넣을거 같았기에, 체력과 내구도를 포함해서 Dijkstra 같은 구현을 했다. 체력 + 내구도가 높으면 높을수록 더 멀리 나갈거라는 가정을 전제하에 풀게되었다.
#include <iostream>
#include <bits/stdc++.h>
#define endl "\n"
#define MAX 100010
using namespace std;
int N, H, D; //변의 길이, 체력, 내구도
char matrix[501][501];
int visited[501][501];
pair<int,int> start;
vector<pair<int,int>> dir = {{0,1},{0,-1},{1,0},{-1,0}};
struct Person{
pair<int,int> loc;
int health;
bool umbrella;
int power;
int distance;
};
void Input(){
cin >> N >> H >> D;
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
cin >> matrix[i][j];
if(matrix[i][j] == 'S') start = {i,j};
//if(matrix[i][j] == 'E') ending = {i,j};
}
}
}
void Solution(){
memset(visited,-1,sizeof(visited));
queue<Person> q;
q.push({start,H,false,0,0});
visited[start.first][start.second] = INT_MAX;
int answer = -1;
while(!q.empty()){
int size = q.size();
for(int i = 0; i < size; i++){
Person first = q.front();
q.pop();
// if(matrix[x][y] == 'E'){
// cout << distance;
// return;
// }
// if(matrix[x][y] == 'U'){
// health += 1;
// umbrella = true;
// power = D;
// }
// if(power <= 0) umbrella = false;
// if(health <= 0) continue;
for(pair<int,int>& p : dir){
int x = first.loc.first, y = first.loc.second, health = first.health, power = first.power;
int distance = first.distance;
bool umbrella = first.umbrella;
int nX = x + p.first;
int nY = y + p.second;
if(nX < 0 || nX >= N || nY < 0 || nY >= N) continue;
if(matrix[nX][nY] == 'E'){
cout << distance + 1;
return;
}
if(matrix[nX][nY] == 'U'){
power = D;
}
if(power != 0){
power--;
}
else{
health--;
}
//cout << x << ' ' << y << ' ' << health << ' ' << power << endl;
if(health == 0) continue;
if(visited[nX][nY] < (health + power)){
visited[nX][nY] = health + power;
q.push({{nX,nY},health,umbrella,power,distance+1});
//if(umbrella) q.push({{nX,nY},health,umbrella,power-1,distance+1});
//if(!umbrella) q.push({{nX,nY},health-1,umbrella,power,distance+1});
}
}
}
}
cout << answer;
}
void Solve(){
Input();
Solution();
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen("input.txt", "r", stdin);
Solve();
return 0;
}