Submission #716663

#	Time	Username	Problem	Language	Result	Execution time	Memory
716663		xyzxyz	Mecho (IOI09_mecho)	C++14	84 / 100	169 ms	9268 KiB

mecho

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> first_biene;
pair<int,int> zuhause;
int s,n;
vector<vector<int>> dist;


bool erreichbar(int i, int j, int zeit, int gemachte_schritte){
	//cout << i << " " << j << " " << gemachte_schritte << " " << zeit << endl;
	/*dist[i][j] = zeit;
	if(i == zuhause.first && j==zuhause.second) return true;
	if (gemachte_schritte >= s){
		zeit++;
		gemachte_schritte = 0;
	}
	if (first_biene[i][j] <= zeit){
		return false;
	}
	bool tmp = false;
	if(!tmp && dist[i-1][j]>=zeit) tmp = erreichbar(i-1, j, zeit, gemachte_schritte+1);
	if(!tmp && dist[i+1][j]>=zeit) tmp = erreichbar(i+1, j, zeit, gemachte_schritte+1);
	if(!tmp && dist[i][j+1]>=zeit) tmp = erreichbar(i, j+1, zeit, gemachte_schritte+1);
	if(!tmp && dist[i][j-1]>=zeit) tmp = erreichbar(i, j-1, zeit, gemachte_schritte+1);
	return tmp;*/
	vector<vector<int>> erreicht(n+2, vector<int>(n+2, 1e9));
	queue<pair<int,int>> next;
	next.push({i,j});
	erreicht[i][j] = zeit*s;
	while(!next.empty()){
        int i1 = next.front().first, j1 = next.front().second;
        //cout << i1 << " " << j1 << endl;
        next.pop();
        //cout << erreicht[i1][j1]+1 << " " << first_biene[i1][j1+1]*s << " " << erreicht[i1][j1+1] << endl;
        if(i1+1==zuhause.first && j1 == zuhause.second) return true;
        else if(i1==zuhause.first && j1+1 == zuhause.second) return true;
        else if(i1-1==zuhause.first && j1 == zuhause.second) return true;
        if(i1==zuhause.first && j1-1 == zuhause.second) return true;
        if(erreicht[i1][j1]+1 < first_biene[i1][j1+1]*s && erreicht[i1][j1]+1<erreicht[i1][j1+1]){
            erreicht[i1][j1+1] = erreicht[i1][j1]+1;
            next.push({i1, j1+1});
        }
        if(erreicht[i1][j1]+1 < first_biene[i1][j1-1]*s && erreicht[i1][j1]+1<erreicht[i1][j1-1]){
            erreicht[i1][j1-1] = erreicht[i1][j1]+1;
            next.push({i1, j1-1});
        }
        if(erreicht[i1][j1]+1 < first_biene[i1+1][j1]*s && erreicht[i1][j1]+1<erreicht[i1+1][j1]){
            erreicht[i1+1][j1] = erreicht[i1][j1]+1;
            next.push({i1+1, j1});
        }
        if(erreicht[i1][j1]+1 < first_biene[i1-1][j1]*s && erreicht[i1][j1]+1<erreicht[i1-1][j1]){
            erreicht[i1-1][j1] = erreicht[i1][j1]+1;
            next.push({i1-1, j1});
        }
	}
	/*for(vector<int> k: erreicht){
        for(int h: k) cout << h << " ";
        cout << endl;
	}*/
	return false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	pair<int,int> start;
	cin >> n >> s;
	vector<vector<char>> karte(n+2, vector<char>(n+2, 'T'));
	first_biene = vector<vector<int>>(n+2, vector<int>(n+2,-1));
	queue<pair<int,pair<int,int>>> bienen;
	for (int i = 1; i <= n; i++){
		for(int j=1; j<=n; j++){
			cin >> karte[i][j];
			if(karte[i][j]=='M'){
				start = {i,j};
				karte[i][j] = 'G';
			}else if(karte[i][j] == 'D') zuhause = {i,j};
			else if(karte[i][j] == 'T'){
				first_biene[i][j] = 0;
			}else if(karte[i][j] == 'H'){
				first_biene[i][j] = 0;
				bienen.push({0,{i,j}});
			}
		}
	}
	while(!bienen.empty()){
		int zeitpunkt = bienen.front().first;
		int i = bienen.front().second.first, j = bienen.front().second.second;
		//cout << zeitpunkt << " " << i << " " << j << endl;
		bienen.pop();
		if(karte[i][j-1]=='G' && (first_biene[i][j-1]==-1 || zeitpunkt+1<first_biene[i][j-1])){
			///cout << "   " << i << " " << j-1 << endl;
			first_biene[i][j-1] = zeitpunkt+1;
			bienen.push({zeitpunkt+1, {i,j-1}});
		}
		if(karte[i-1][j]=='G' && (zeitpunkt+1 < first_biene[i-1][j] || first_biene[i-1][j] == -1)){
			//cout << "   " << i-1 << " " << j << endl;
			first_biene[i-1][j] = zeitpunkt+1;
			bienen.push({zeitpunkt+1, {i-1, j}});
		}
		if(karte[i+1][j]=='G' && (zeitpunkt+1 < first_biene[i+1][j] || first_biene[i+1][j] == -1)){
			//cout << "   " << i+1 << " " << j << endl;
			first_biene[i+1][j] = zeitpunkt+1;
			bienen.push({zeitpunkt+1, {i+1,j}});
		}
		if(karte[i][j+1]=='G' && (zeitpunkt+1 < first_biene[i][j+1] || first_biene[i][j+1] == -1)){
			//cout << "   " << i << " " << j+1 << endl;
			first_biene[i][j+1] = zeitpunkt+1;
			bienen.push({zeitpunkt+1, {i, j+1}});
		}
	}
	/*for (auto y : first_biene){
		for (auto x : y){
			cout << x << " ";
		}
		cout << endl;
	}
	*/
	int lower = 0, upper = first_biene[start.first][start.second];
	while(lower<=upper){
		int zeit = (upper+lower)/2;
		//cout << "Zeit: " << zeit << endl;
		dist = vector<vector<int>>(n+2, vector<int>(n+2, 1e9));
		if(erreichbar(start.first, start.second, zeit, 0)){
			//cout << "erreicht: " << zeit << endl;
			lower = zeit+1;
		}else{//nicht erreichbar in Zeit
			//cout << "nicht: " << zeit << endl;
			upper = zeit-1;
		}
		//cout << endl;
	}
	//cout << lower << " " << upper << endl;
	dist = vector<vector<int>>(n+2, vector<int>(n+2, 1e9));
	if(lower == 0 && !erreichbar(start.first, start.second, 0, 0)) cout << "-1" << endl;
	else cout << lower-1;

	return 0;
}

/*
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 0 0 0 0 0 0 0 -1
-1 0 5 5 5 5 5 0 -1
-1 0 4 4 4 4 4 0 -1
-1 4 3 3 3 3 3 -1 -1
-1 0 2 2 2 2 2 0 -1
-1 0 1 1 1 1 1 0 -1
-1 0 0 0 0 0 0 0 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
*/

• Subtask 1: 84 / 100