oj.uz

답안 #138704

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
138704 2019-07-30T08:51:23 Z Boxworld Mecho (IOI09_mecho) C++14
14 / 100
 1000 ms 9720 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MX=1000,inf=0x7fffffff;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
char G[MX][MX];
int d[MX][MX],d1[MX][MX];
int n,s,sx,sy,fx,fy,ans=-1;
queue<int> Q1[2];
int bfs(int time){
	memset(d1,0,sizeof(d1));
	d1[sx][sy]=-1;
	queue<int> Q;
	Q.push(sx*MX+sy);
	while(!Q.empty()){
		int x=Q.front()/MX,y=Q.front()%MX;Q.pop();
	//	printf("x=%d,y=%d time=%d\n",x,y,d1[x][y]/s+time);
		if (time>0&&d1[x][y]/s+time>=d[x][y])continue;
		for (int i=0;i<4;i++){
			int X=x+dx[i],Y=y+dy[i];
			if (X<1||X>n||Y<1||Y>n)continue;
			if (X==fx&&Y==fy)return 1;
			if (G[X][Y]=='T'||G[X][Y]=='H'||d1[X][Y]>0)continue;
			d1[X][Y]=d1[x][y]+1;
			Q.push(X*MX+Y);
	//		printf("INQ T:%d X:%d Y:%d\n",d1[X][Y],X,Y);
		}
	//	printf("#\n");
	//	for (int i=1;i<=n;i++){
	//		for (int j=1;j<=n;j++)printf("%2d",d1[i][j]);printf("\n");
	//	}
	}
	return 0;
}
int main(){
	scanf("%d%d",&n,&s);
	memset(d,-1,sizeof(d));
	for (int i=1;i<=n;i++){
		scanf("%s",G[i]+1);
		for (int j=1;j<=n;j++){
			if (G[i][j]=='H')d[i][j]=0,Q1[0].push(i*MX+j);
			if (G[i][j]=='M')sx=i,sy=j;
			if (G[i][j]=='D')d[i][j]=inf,fx=i,fy=j;
		}
	}
	
	int cnt=0;
	for (int t=1;;t++){
		if (Q1[cnt].empty())break;
		while(!Q1[cnt].empty()){
			int xy=Q1[cnt].front();Q1[cnt].pop();
			int x=xy/MX,y=xy%MX;
			for (int i=0;i<4;i++){
				int X=x+dx[i],Y=y+dy[i];
				if (d[X][Y]>=0||G[X][Y]=='D'||G[X][Y]=='T')continue;
				d[X][Y]=t;
				Q1[1-cnt].push(X*MX+Y);
			}
		}
		cnt=1-cnt;
	}
	
	for (int t=d[sx][sy];t>=0;t--)
	if (bfs(t)){
		printf("%d\n",t);
		return 0;
	}
	printf("-1");
/*	if (bfs(-1)){
		ans=0;
		int l=0,m,r=d[sx][sy];
		while(l<r){
			m=(l+r)/2;
			if (bfs(m)){
				l=m+1;
				ans=m;
			}else{
				r=m-1;
			}
		}
	}
	printf("%d\n",ans);*/
	return 0;
}

Compilation message

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

Subtask #1
14.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 30 ms 8184 KB Output isn't correct
2 Incorrect 31 ms 8136 KB Output isn't correct
3 Incorrect 31 ms 8188 KB Output isn't correct
4 Incorrect 30 ms 8184 KB Output isn't correct
5 Correct 31 ms 8184 KB Output is correct
6 Correct 30 ms 8184 KB Output is correct
7 Execution timed out 1067 ms 9080 KB Time limit exceeded
8 Incorrect 32 ms 8188 KB Output isn't correct
9 Correct 30 ms 8184 KB Output is correct
10 Correct 31 ms 8184 KB Output is correct
11 Correct 32 ms 8184 KB Output is correct
12 Incorrect 33 ms 8184 KB Output isn't correct
13 Correct 35 ms 8184 KB Output is correct
14 Incorrect 38 ms 8184 KB Output isn't correct
15 Incorrect 28 ms 8184 KB Output isn't correct
16 Incorrect 30 ms 8184 KB Output isn't correct
17 Incorrect 30 ms 8184 KB Output isn't correct
18 Incorrect 31 ms 8184 KB Output isn't correct
19 Incorrect 30 ms 8184 KB Output isn't correct
20 Incorrect 30 ms 8204 KB Output isn't correct
21 Incorrect 31 ms 8184 KB Output isn't correct
22 Incorrect 30 ms 8184 KB Output isn't correct
23 Incorrect 29 ms 8188 KB Output isn't correct
24 Incorrect 31 ms 8184 KB Output isn't correct
25 Incorrect 31 ms 8188 KB Output isn't correct
26 Incorrect 31 ms 8184 KB Output isn't correct
27 Incorrect 32 ms 8184 KB Output isn't correct
28 Incorrect 31 ms 8184 KB Output isn't correct
29 Incorrect 31 ms 8312 KB Output isn't correct
30 Incorrect 31 ms 8312 KB Output isn't correct
31 Incorrect 30 ms 8184 KB Output isn't correct
32 Incorrect 29 ms 8312 KB Output isn't correct
33 Incorrect 30 ms 8696 KB Output isn't correct
34 Incorrect 31 ms 8696 KB Output isn't correct
35 Correct 476 ms 8696 KB Output is correct
36 Incorrect 34 ms 8652 KB Output isn't correct
37 Incorrect 32 ms 8696 KB Output isn't correct
38 Correct 754 ms 8716 KB Output is correct
39 Incorrect 30 ms 8700 KB Output isn't correct
40 Incorrect 30 ms 8696 KB Output isn't correct
41 Execution timed out 1037 ms 8696 KB Time limit exceeded
42 Incorrect 32 ms 8824 KB Output isn't correct
43 Incorrect 29 ms 8828 KB Output isn't correct
44 Execution timed out 1082 ms 8792 KB Time limit exceeded
45 Incorrect 31 ms 8828 KB Output isn't correct
46 Incorrect 28 ms 8832 KB Output isn't correct
47 Execution timed out 1059 ms 8824 KB Time limit exceeded
48 Incorrect 29 ms 8824 KB Output isn't correct
49 Incorrect 29 ms 8824 KB Output isn't correct
50 Execution timed out 1059 ms 8824 KB Time limit exceeded
51 Incorrect 29 ms 9080 KB Output isn't correct
52 Incorrect 30 ms 9080 KB Output isn't correct
53 Execution timed out 1052 ms 9080 KB Time limit exceeded
54 Incorrect 31 ms 9084 KB Output isn't correct
55 Incorrect 31 ms 9048 KB Output isn't correct
56 Execution timed out 1068 ms 9208 KB Time limit exceeded
57 Incorrect 31 ms 9128 KB Output isn't correct
58 Incorrect 30 ms 9080 KB Output isn't correct
59 Execution timed out 1051 ms 9208 KB Time limit exceeded
60 Incorrect 31 ms 9208 KB Output isn't correct
61 Incorrect 32 ms 9160 KB Output isn't correct
62 Execution timed out 1063 ms 9208 KB Time limit exceeded
63 Correct 341 ms 9240 KB Output is correct
64 Execution timed out 1073 ms 9208 KB Time limit exceeded
65 Execution timed out 1049 ms 9208 KB Time limit exceeded
66 Incorrect 985 ms 9352 KB Output isn't correct
67 Execution timed out 1055 ms 9284 KB Time limit exceeded
68 Correct 170 ms 9376 KB Output is correct
69 Correct 72 ms 9340 KB Output is correct
70 Incorrect 138 ms 9336 KB Output isn't correct
71 Incorrect 113 ms 9336 KB Output isn't correct
72 Incorrect 334 ms 9376 KB Output isn't correct
73 Correct 45 ms 9432 KB Output is correct
74 Correct 456 ms 9508 KB Output is correct
75 Correct 915 ms 9636 KB Output is correct
76 Correct 778 ms 9720 KB Output is correct
77 Correct 751 ms 9720 KB Output is correct
78 Execution timed out 1076 ms 9592 KB Time limit exceeded
79 Correct 239 ms 9592 KB Output is correct
80 Correct 547 ms 9628 KB Output is correct
81 Execution timed out 1083 ms 9592 KB Time limit exceeded
82 Correct 596 ms 9720 KB Output is correct
83 Execution timed out 1088 ms 9592 KB Time limit exceeded
84 Correct 872 ms 9692 KB Output is correct
85 Correct 489 ms 9692 KB Output is correct
86 Execution timed out 1080 ms 9592 KB Time limit exceeded
87 Execution timed out 1073 ms 9596 KB Time limit exceeded
88 Execution timed out 1079 ms 9592 KB Time limit exceeded
89 Execution timed out 1075 ms 9592 KB Time limit exceeded
90 Execution timed out 1071 ms 9592 KB Time limit exceeded
91 Execution timed out 1079 ms 9464 KB Time limit exceeded
92 Execution timed out 1069 ms 9592 KB Time limit exceeded