2차원 지도가 주어진다.
세준이는 [0,0]에서 시작하여 인접한 좌표중 차이가 T이하인 곳으로 이동할 수 있다.
높은곳으로 이동하는 경우는 차이의 제곱만큼, 아닌 경우는 1만큼 시간이 소모된다.
D초 이하의 시간동안 다시 돌아올 수 있는 위치중 최고 높은 위치를 구하는 문제이다.
1. 다익스트라 풀이
[0,0]에서 갈 수 있는 최단경로들을 구하고 반대로 [0,0]으로 올 수 있는 최단 경로들을 구한다.
돌아오는 경우도 [0,0]에서 돌리되 주어진 정보와 반대로 cost를 주어야 한다.
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;
inline int ipow(int x) { return x*x; }
int N, M, T, D;
char map[25][25];
int imap[25][25];
int dy[] = { -1,0,0,1 };
int dx[] = { 0,1,-1,0 };
int d[626], rd[626];
vector<pair<int, int>> adj[626], rev_adj[626];
void solve(vector<pair<int, int>> vect[626], int dist[626]) {
priority_queue<pair<int, int>> pq;
pq.push({ 0,0 });
dist[0] = 0;
while (!pq.empty()) {
int here = pq.top().second;
int time = -pq.top().first;
pq.pop();
if (dist[here] < time) continue;
for (auto n : vect[here]) {
int next = n.second;
if (dist[next] > time + n.first) {
dist[next] = time + n.first;
pq.push({ -dist[next], next });
}
}
}
}
int main() {
memset(d, 0x3f, sizeof d);
memset(rd, 0x3f, sizeof rd);
scanf("%d%d%d%d", &N, &M, &T, &D);
for (int n = 0;n < N;n++) scanf("%s", &map[n]);
for (int n = 0;n < N;n++) {
for (int m = 0;m < M;m++) {
if (map[n][m] >= 'A' && map[n][m] <= 'Z')
imap[n][m] = map[n][m] - 'A';
else
imap[n][m] = map[n][m] - 'a' + 26;
}
}
for (int n = 0;n < N;n++) {
for (int m = 0;m < M;m++) {
for (int i = 0;i < 4;i++) {
int y = n + dy[i], x = m + dx[i];
if (y < 0 || y >= N || x < 0 || x >= M) continue;
int start = imap[n][m], end = imap[y][x];
if (abs(start - end) > T) continue;
if (start >= end) adj[n*M + m].emplace_back(make_pair(1, y*M + x));
else adj[n*M + m].emplace_back(make_pair(ipow(start - end), y*M + x));
if(start > end) rev_adj[n*M + m].emplace_back(make_pair(ipow(start - end), y*M + x));
else rev_adj[n*M + m].emplace_back(make_pair(1, y*M + x));
}
}
}
solve(adj, d);
solve(rev_adj, rd);
int ans = imap[0][0];
for (int n = 0;n < N;n++) {
for (int m = 0;m < M;m++) {
if (d[n*M + m] + rd[n*M + m] <= D) {
ans = max(ans, imap[n][m]);
}
}
}
printf("%d\n", ans);
return 0;
}
| cs |
2. 플로이드 와샬 풀이
최대로 정점이 들어온다면 $O(N^{3}M^{3})$의 복잡도를 가지지만 시간안에 통과된다.
방법은 위의 방법과 동일하다.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 987654321
int N, M, T, D;
char map[26][26];
int adj[666][666];
int dy[] = { -1,0,0,1 }, dx[] = { 0,1,-1,0 };
int getAlpha(int y, int x) {
if (map[y][x] >= 'a' && map[y][x] <= 'z') {
return map[y][x] - 'a' + 26;
}
else{
return map[y][x] - 'A';
}
}
int main() {
scanf("%d%d%d%d", &N, &M, &T, &D);
for (int n = 0;n < N;n++)
scanf("%s", map[n]);
for (int n = 0;n < N*M;n++)
for (int m = 0;m < N*M;m++)
adj[n][m] = n == m ? 0 : INF;
for (int n = 0;n < N;n++) {
for (int m = 0;m < M;m++) {
int here = n*M + m;
for (int i = 0;i < 4;i++) {
int y = n + dy[i], x = m + dx[i];
if (y < 0 || y >= N || x < 0 || x >= M) continue;
int next = y*M + x;
int diff = getAlpha(n, m) - getAlpha(y, x);
if (abs(diff) > T) continue;
if (diff > 0) { //내리막
adj[here][next] = 1;
}
else if (diff < 0) { //오르막
adj[here][next] = diff*diff;
}
else {
adj[here][next] = 1;
}
}
}
}
int MAX = N*M;
for (int k = 0;k < MAX;k++) {
for (int n = 0;n < MAX;n++) {
for (int m = 0;m < MAX;m++) {
if (adj[n][m] > adj[n][k] + adj[k][m]) {
adj[n][m] = adj[n][k] + adj[k][m];
}
}
}
}
int ans = 0;
for (int n = 0;n < MAX;n++) {
if (adj[0][n] + adj[n][0] <= D) {
ans = max(ans, getAlpha(n / M, n%M));
}
}
printf("%d\n", ans);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기