제출 #763893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
763893		hanlulu	Mecho (IOI09_mecho)	C++14	30 / 100	186 ms	6748 KiB

mecho

//https://cses.fi/problemset/task/1707
#include <bits/stdc++.h>
using namespace std; 
/*
有点像793的题目，两次最短。Bee走出到每一个位置的最短，
然后二分答案，然后Mecho走最短的时侯每一个相邻是否可以走需要计算是否Bee先到。
如何处理一分钟走s步这里？dis记录当前的步数，每次走到相邻+1，但是时间可以用dis/s得到。
*/
int n,s;
char a[801][801];
int rdir[4] = {0,0,1,-1};
int cdir[4] = {1,-1,0,0};
vector<vector<int>> beetime(801,vector<int>(801,1e9));

int sx,sy,ex,ey;//起点和终点 

bool isok(int eat)//eat is how many time he stay at start point. 
{
	vector<vector<int>> mstep(801,vector<int>(801,1e9));
	//cout << eat << endl;
	queue<pair<int,int>> myq;
	mstep[sx][sy] = 0;
	myq.push({sx,sy}); 
	while (!myq.empty()) {
		int x = myq.front().first;
		int y = myq.front().second;
		myq.pop();
		for (int i = 0; i < 4; i++)
		{
			int newx = x + rdir[i];
			int newy = y + cdir[i];
			if (newx <0 || newx == n || newy < 0 || newy == n) continue;
			if (a[newx][newy] == 'T' || a[newx][newy] == 'H') continue;
			if (mstep[newx][newy] <= mstep[x][y] + 1) continue;
			if (beetime[newx][newy] < ceil(1.0*(mstep[x][y]+1) /s) + eat) continue; 
			//cout << newx << " " << newy << " " << (mstep[x][y]+1) /s + eat << endl;
			mstep[newx][newy] = mstep[x][y] + 1;
			//if (a[newx][newy] == 'D') break; 
			myq.push({newx,newy});
		}		
	}
	//cout <<  mstep[2][2]  << endl;
	return mstep[ex][ey] != 1e9;
}
int main()
{
  //	ios::sync_with_stdio(false);
//	cin.tie(0);
	//cout.tie(0);
	//freopen("nocross.in","r",stdin);
	//freopen("nocross.out","w",stdout);
 	cin >> n >> s;
	
	queue<pair<int,int>> myq;
 	for (int i = 0; i < n; i++) 
 	for (int j = 0; j < n; j++) 
 	{
 		cin >> a[i][j];
 		if (a[i][j] == 'M') sx = i, sy = j;
 		if (a[i][j] == 'D') ex = i, ey = j;
 		if (a[i][j] == 'H') {
 			beetime[i][j] = 0;
 			myq.push({i,j});
		};
	}	

  	//find beetime
	while (!myq.empty()) {
		int x = myq.front().first;
		int y = myq.front().second;
		myq.pop();
		for (int i = 0; i < 4; i++)
		{
			int newx = x + rdir[i];
			int newy = y + cdir[i];
			if (newx <0 || newx == n || newy < 0 || newy == n) continue;
			if (a[newx][newy] == 'T' ||  a[newx][newy] == 'H') continue;
			if (beetime[newx][newy] <= beetime[x][y] + 1) continue;
			
			beetime[newx][newy] = beetime[x][y] + 1;
			
			if (a[newx][newy] != 'D' )//can not go throuh home, but need know the time bee arrive
 				myq.push({newx,newy});
		}
	}
	  //	cout << beetime[2][2]<< endl;
  	//bin the answer
  	int ans = -1;
  	int l = 0, r =  n*n, mid;
  	while (l <= r) {
  		mid = (l+r)/2;
  		//cout << "mid " << mid <<  endl;
		if (isok(mid)) {
			ans = mid;
			l = mid + 1;
		}	
		else r = mid - 1;
	}
	cout << ans << '\n'; 
	return 0;
}

• Subtask 1: 30 / 100