제출 #835404

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
835404		mohammad_kilani	Mecho (IOI09_mecho)	C++17	100 / 100	125 ms	6384 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' ||  grid[nr][nc] == 'D' || 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(row == er && col == ec)
			return true;
		if(cost2[row][col] >= cost[row][col] * s) 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));
		}
	}
	return false;
}

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 = cost[sr][sc] - 1 , 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;
} 

컴파일 시 표준 에러 (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: 100 / 100