Submission #835358

#	Time	Username	Problem	Language	Result	Execution time	Memory
835358		mohammad_kilani	Mecho (IOI09_mecho)	C++17	95 / 100	151 ms	6304 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define oo 1000000010

const int N = 810;

int n , s;

char grid[N][N];

int cost[N][N];

int dr[] = {0 , 1,  0 , -1};
int dc[] = {1 , 0 , -1 , 0};

int sr , sc , er , ec;

int cost2[N][N];

void BFSH(){
	queue < pair< int , int > > q;
	memset(cost , -1, sizeof(cost));
	for(int i = 0;i < n;i++){
		for(int j = 0 ;j < n;j++){
			if(grid[i][j] == 'H'){
				q.push(make_pair(i , j));
				cost[i][j] = 0;
			}
		}
	}
	int row , col;
	while(!q.empty()){
		row = q.front().first;
		col = q.front().second;
		q.pop();
		for(int nr , nc , i = 0 ;i < 4;i++){
			nr = row + dr[i];
			nc = col + dc[i];
			if(nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] == 'T' || cost[nr][nc] != -1) continue;
			cost[nr][nc] = cost[row][col] + 1;
			q.push(make_pair(nr , nc));
		}
	}
}

bool check(int mid){
	for(int i = 0 ;i < n;i++) for(int j = 0 ;j < n;j++) cost2[i][j] = -1;
	cost2[sr][sc] = mid * s;
	queue < pair< int , int > > q;
	q.push(make_pair(sr, sc));
	int row , col;
	while(!q.empty()){
		row = q.front().first;
		col = q.front().second;
		q.pop();
		if((cost2[row][col] / s) >= cost[row][col]) continue;
		for(int nr , nc , i = 0 ;i < 4;i++){
			nr = row + dr[i];
			nc = col + dc[i];
			if(nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] == 'T' || cost2[nr][nc] != -1) continue;
			cost2[nr][nc] = cost2[row][col] + 1;
			q.push(make_pair(nr , nc));
		}
	}
	if(cost2[er][ec] == -1)
		return false;
	return true;
}

int main(){
	scanf("%d%d",&n,&s);
	for(int i = 0 ;i < n;i++){
		scanf("%s",grid[i]);
		for(int j = 0 ;j < n;j++){
			if(grid[i][j] == 'M')
				sr = i , sc = j;
			if(grid[i][j] == 'D')
				er = i , ec = j;
		}
	}
	BFSH();

	int low = 0 , high = n * n , mid , ans = -1;

	while(high >= low){
		mid = (low + high) / 2;
		if(check(mid))
			ans = mid , low = mid + 1;
		else
			high = mid - 1;
	}
	cout << ans << endl;
	return 0;
} 

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |  scanf("%d%d",&n,&s);
      |  ~~~~~^~~~~~~~~~~~~~
mecho.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   scanf("%s",grid[i]);
      |   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 95 / 100