제출 #309220

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
309220		sofapuden	Mecho (IOI09_mecho)	C++14	15 / 100	813 ms	65540 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

int n, k;
bool ok = 0;

pair<int,int> sta, en;

vector<string> G;
vector<vector<int>> V;
vector<vector<int>> vis;

queue<pair<pair<int,int>,int>> Q;

auto cmp = [](pair<pair<int,int>,pair<int,int>> l, pair<pair<int,int>,pair<int,int>> r){
	if(l.f.f != r.f.f)return l.f.f < r.f.f;
	return l.f.s > r.f.s;
};
priority_queue<pair<pair<int,int>,pair<int,int>>, vector<pair<pair<int,int>,pair<int,int>>>, decltype(cmp)> PQ(cmp);

void fin(pair<pair<int,int>,pair<int,int>> now){
	if(vis[now.s.f][now.s.s] < now.f.s)return;
	vis[now.s.f][now.s.s] = now.f.s;
	if(now.s == en){cout << now.f.f << "\n";ok = 1;return;}
	if(now.s.f != n-1){
		if(V[now.s.f+1][now.s.s] > now.f.s/k+now.f.s/k-1){
			PQ.push({{min(V[now.s.f+1][now.s.s]-now.f.s/k-1,now.f.f), now.f.s+1},{now.s.f+1,now.s.s}});
		}
	}
	if(now.s.s != n-1){
		if(V[now.s.f][now.s.s+1] > now.f.s/k+now.f.s/k-1){
			PQ.push({{min(V[now.s.f][now.s.s+1]-now.f.s/k-1,now.f.f), now.f.s+1},{now.s.f,now.s.s+1}});
		}
	}
	
	if(now.s.f != 0){
		if(V[now.s.f-1][now.s.s] > now.f.s/k+now.f.s/k-1){
			PQ.push({{min(V[now.s.f-1][now.s.s]-now.f.s/k-1,now.f.f), now.f.s+1},{now.s.f-1,now.s.s}});
		}
	}
	
	if(now.s.s != 0){
		if(V[now.s.f][now.s.s-1] > (now.f.s/k)+now.f.s/k-1){
			PQ.push({{min(V[now.s.f][now.s.s-1]-now.f.s/k-1,now.f.f), now.f.s+1},{now.s.f,now.s.s-1}});
		}
	}

			
}
	
	
	

void search(pair<pair<int,int>,int> now){
	if(now.f.f < 0 || now.f.s < 0 || now.f.f >= n || now.f.s >= n)return;
	if(V[now.f.f][now.f.s] != -1)return;
	V[now.f.f][now.f.s] = now.s;
	Q.push({{now.f.f-1,now.f.s},now.s+1});
	Q.push({{now.f.f+1,now.f.s},now.s+1});
	Q.push({{now.f.f,now.f.s-1},now.s+1});
	Q.push({{now.f.f,now.f.s+1},now.s+1});
}

int main(){ 
	cin >> n >> k;
	G.resize(n);
	V.resize(n, vector<int> (n,-1));
	vis.resize(n, vector<int> (n, 100000));
	
	for(auto &x : G)cin >> x;
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			if(G[i][j] == 'T')V[i][j] = -2;
			if(G[i][j] == 'M')sta = {i,j};
			if(G[i][j] == 'D'){en = {i,j};V[i][j] = 100000;}
			if(G[i][j] == 'H')Q.push({{i,j},0});
		}
	}
	while(!Q.empty()){
		auto x = Q.front();
		Q.pop();
		search(x);
	}
	//for(int i = 0; i < n; ++i){
		//for(int j = 0; j < n; ++j){
			//cout << V[i][j] << " ";
		//}
		//cout << "\n";
	//}
	PQ.push({{V[sta.f][sta.s], 0},sta});
	while(!PQ.empty()){
		auto x = PQ.top();
		PQ.pop();
		//cout << x.f.f << " " << x.f.s << " " << x.s.f << " " << x.s.s << "\n";
		fin(x);
		if(ok)break;
	}
	if(!ok)cout << -1 << "\n";
}
	
	
	

• Subtask 1: 15 / 100