제출 #545004

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
545004		MilosMilutinovic	Mecho (IOI09_mecho)	C++14	100 / 100	166 ms	6304 KiB

mecho

#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<typename T> bool chkmin(T&x,T y){return x>y?x=y,1:0;}
template<typename T> bool chkmax(T&x,T y){return x<y?x=y,1:0;}

int n,s,sx,sy,ex,ey,dist[805][805],dis[805][805];
char base[805][805];
const int dir[4][2]={0,1,0,-1,1,0,-1,0};

void bfs(){
	memset(dist,-1,sizeof dist);
	queue<pii> que;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(base[i][j]=='H') que.push(mp(i,j)),dist[i][j]=0;
	while(!que.empty()){
		int i=que.front().fi;
		int j=que.front().se;
		que.pop();
		for(int k=0;k<4;k++){
			int ni=i+dir[k][0];
			int nj=j+dir[k][1];
			if(ni>=1&&ni<=n&&nj>=1&&nj<=n&&(base[ni][nj]=='G'||base[ni][nj]=='M')&dist[ni][nj]==-1){
				que.push(mp(ni,nj)); dist[ni][nj]=dist[i][j]+s;
			}
		}
	}
}

bool check(int t){
	if(dist[sx][sy]<=t*s) return false;
	memset(dis,-1,sizeof dis);
	queue<pii> que;
	que.push(mp(sx,sy)); dis[sx][sy]=t*s;
	while(!que.empty()){
		int i=que.front().fi;
		int j=que.front().se;
		que.pop();
		for(int k=0;k<4;k++){
			int ni=i+dir[k][0];
			int nj=j+dir[k][1];
			if(ni>=1&&ni<=n&&nj>=1&&nj<=n&&dis[ni][nj]==-1&&(base[ni][nj]=='D'||(base[ni][nj]=='G'&&dist[ni][nj]>dis[i][j]+1))){
				que.push(mp(ni,nj)); dis[ni][nj]=dis[i][j]+1;
			}
		}
	}
	return dis[ex][ey]!=-1;
}

int main(){
	scanf("%d%d",&n,&s);
	for(int i=1;i<=n;i++){
		scanf("%s",base[i]+1);
		for(int j=1;j<=n;j++){
			if(base[i][j]=='M') sx=i,sy=j;
			if(base[i][j]=='D') ex=i,ey=j;
		}
	}
	bfs();
	int l=-1,r=n*n+5,ans=-1;
	while(l<=r){
		int m=(l+r)/2;
		if(check(m)) ans=m,l=m+1; else r=m-1;
	}
	printf("%d",ans);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

mecho.cpp: In function 'void bfs()':
mecho.cpp:33:86: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   33 |    if(ni>=1&&ni<=n&&nj>=1&&nj<=n&&(base[ni][nj]=='G'||base[ni][nj]=='M')&dist[ni][nj]==-1){
      |                                                                          ~~~~~~~~~~~~^~~~
mecho.cpp: In function 'int main()':
mecho.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  scanf("%d%d",&n,&s);
      |  ~~~~~^~~~~~~~~~~~~~
mecho.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |   scanf("%s",base[i]+1);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100