그래프의 간선 가중치에 대해 조금만 생각해보면 핵심적인 아이디어를 떠올릴 수 있습니다.
간선의 존재여부 및 그 가중치를 인접행렬이나 인접리스트로 저장하는 대신, 인접한 두 위치와 그 높이를 갖고 간선 존재여부 및 가중치를 O(1)에 계산할 수 있습니다.
이 격자 그래프에서 노드의 개수는 최대 625개이고, 간선의 수도 이에 선형비례하므로 다익스트라 알고리즘을 사용해 준다면 시작점에서 모든 노드로 가는 최단시간을 파악할 수 있습니다.
한 가지 문제점은 우리가 고려할 경로는 가는 경로뿐만 아니라 오는 경로도 있다는 것이지만, 이는 간선 가중치를 부여할 때 간선의 시작점과 끝점을 뒤집어 가중치를 판단함으로써 해결 가능합니다.
이에 따라 시작점에서 모든 점까지의, 모든 점에서 시작점까지의 최단경로를 구할 수 있고 이것의 합이 제한 시간보다 작은 노드 중 높이가 최대인 노드를 찾으면 됩니다.
이것을 코드로 옮기면 다음과 같이 작성할 수 있습니다.
#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using dat=pair<int,pii>;
const int inf=0x3f3f3f3f;
int n,m,t,d;
string arr[25];
int d1[25][25],d2[25][25];
const int dx[]={0,0,-1,1};
const int dy[]={-1,1,0,0};
int cti(char x){
return (x|32)-'a'+(x&32)/16*13;
}
int vpos(int x,int y){
return x>=0&&x<n&&y>=0&&y<m;
}
int dist(int a,int b,int x,int y){
if(abs(cti(arr[a][b])-cti(arr[x][y]))>t)return inf;
int q=cti(arr[a][b]);//start
int w=cti(arr[x][y]);//end
if(q>=w)return 1;
return (w-q)*(w-q);
}
int main(void){
ios::sync_with_stdio(0);cin.tie(0);
memset(d1,'?',sizeof(d1));
memset(d2,'?',sizeof(d2));
cin>>n>>m>>t>>d;
for(int i=0;i<n;i++)cin>>arr[i];
d1[0][0]=d2[0][0]=0;
{
priority_queue<dat> q;
q.push(dat(-0,pii(0,0)));
while(!q.empty()){
int dst,a,b;
dst=-q.top().first;
tie(a,b)=q.top().second;
q.pop();
dst=-dst;
if(dst>d1[a][b])continue;
for(int i=0;i<4;i++){
int nx=a+dx[i];
int ny=b+dy[i];
if(!vpos(nx,ny))continue;
int dd=dist(a,b,nx,ny);
if(d1[nx][ny]>d1[a][b]+dd){
d1[nx][ny]=d1[a][b]+dd;
q.push(dat(-d1[nx][ny],pii(nx,ny)));
}
}
}
}
{
priority_queue<dat> q;
q.push(dat(-0,pii(0,0)));
while(!q.empty()){
int dst,a,b;
dst=-q.top().first;
tie(a,b)=q.top().second;
q.pop();
if(dst>d2[a][b])continue;
for(int i=0;i<4;i++){
int nx=a+dx[i];
int ny=b+dy[i];
if(!vpos(nx,ny))continue;
int dd=dist(nx,ny,a,b);
if(d2[nx][ny]>d2[a][b]+dd){
d2[nx][ny]=d2[a][b]+dd;
q.push(dat(-d2[nx][ny],pii(nx,ny)));
}
}
}
}
int mx=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(d1[i][j]+d2[i][j]>d)continue;
mx=max(mx,cti(arr[i][j]));
}
}
cout<<mx;
}