oj.uz

답안 #946713

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
946713 2024-03-14T23:50:31 Z narsuk Mecho (IOI09_mecho) C++17
38 / 100
 1000 ms 11300 KB 
#include <bits/stdc++.h>
using namespace std;
//
#define ll long long int
 
#define endl "\n"; 
 
const int maxn = 601;

// array<int,n>
// pq 


int n,st;

pair<int,int>mv[4]={ {0,1},{0,-1} , {1,0}, {-1,0} };

char g[maxn][maxn];
char g1[maxn][maxn];
char g2[maxn][maxn];

bool val(int x , int y){
	if(x<0 || x>=n || y<0 || y>=n || g[x][y]=='T')return 0;
	return 1;
}
 

int xc,yc;

void bbfs(int x){
	int vis[n][n];
	queue<pair<pair<int,int>,int>>q;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(g1[i][j]=='H'){
				q.push({{i,j},0});
			}
			vis[i][j]=0;
		}
	}
	while(!q.empty()){
		pair<int,int>cur;
		cur=q.front().first;
		int dt = q.front().second;
		q.pop();
		if(dt>x){
			continue;
		}
		if(vis[cur.first][cur.second])continue;
		vis[cur.first][cur.second]=1;

		if(g1[cur.first][cur.second]=='D' || g1[cur.first][cur.second]=='T'){
			continue;
		} 
		g1[cur.first][cur.second]='H';
		// cout<<cur.first<<" "<<cur.second<<endl;
		for(auto ele : mv){
			int xx = cur.first+ele.first;
			int yy = cur.second+ele.second;
			if(val(xx,yy)){
				q.push({{xx,yy},dt+1});
			}
		}
	}

}




int mbfs(int x){

	int vis[n][n];
	queue<pair<pair<int,int>,int>>q;
	int cou = 0;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			// cout<<g1[i][j];
			if(g1[i][j]=='M'){
				q.push({{i,j},0});
				cou++;
			}
			vis[i][j]=0;
		}
		// cout<<endl;
	}
	// cout<<endl;
	if(cou==0){
		return 0;
	}
	while(!q.empty()){
		pair<int,int>cur;
		cur=q.front().first;
		int dt = q.front().second;
		q.pop();
		if(dt>x){
			continue;
		}
		if(g1[cur.first][cur.second]=='D'){
			return 1;
		}
		if(g1[cur.first][cur.second]!='G' && g1[cur.first][cur.second]!='M'){
			continue;
		}
		if(vis[cur.first][cur.second])continue;
		vis[cur.first][cur.second]=1;
		g1[cur.first][cur.second]='M';
		for(auto ele : mv){
			int xx = cur.first+ele.first;
			int yy = cur.second+ele.second;
			if(val(xx,yy)){
				q.push({{xx,yy},dt+1});
			}
		}
	}
	return 2;

}
 

bool check(int x){
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			g1[i][j]=g[i][j];
		}
	}
	bbfs(x);
	// cout<<"de"<<endl;
	while(1){
		// for(int i=0;i<n;i++){
		// 	for(int j=0;j<n;j++){
		// 		cout<<g1[i][j];
		// 	}
		// 	cout<<endl;
		// }
		// cout<<endl;
		// int cans1 = mbfs(st);
		// cout<<cans1<<endl; 
		// if(cans1==1) return 1; 
		// for(int i=0;i<n;i++){
		// 	for(int j=0;j<n;j++){
		// 		g1[i][j]=g2[i][j];
		// 	}
		// }


		int cans = mbfs(st);
		// cout<<cans<<endl;
		if(cans==0)return 0;
		if(cans==1) return 1; 
		bbfs(1);
	}
}

void solu(){
	cin>>n>>st;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>g[i][j];
			g1[i][j]=g[i][j];
			if(g[i][j]=='M'){
				xc=i;
				yc=j;
			}
		}
	}
	// cout<<endl;
	int l=0;
	int r = 1e6;
	int ans=0;
	while(l<=r){
		int mid = l + (r-l)/2;
		// cout<<mid<<endl;
		if(check(mid)){
			ans=max(mid,ans);
			l=mid+1;
		}else{
			r=mid-1;
		}
	}
	// cout<<check(1)<<endl;
	cout<<ans<<endl;


}
int main(){
		// ios_base::sync_with_stdio(0);
		// cin.tie(0);
		// int cass;
		// cin>>cass; 
		// for(int i=0;i<cass;i++)
		solu();
    return 0;
}

Subtask #1
38.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 412 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Runtime error 17 ms 1960 KB Execution killed with signal 11
8 Incorrect 1 ms 348 KB Output isn't correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 444 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 3 ms 348 KB Output is correct
14 Incorrect 23 ms 604 KB Output isn't correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 3 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 3 ms 348 KB Output is correct
24 Correct 2 ms 348 KB Output is correct
25 Correct 10 ms 348 KB Output is correct
26 Correct 5 ms 348 KB Output is correct
27 Correct 7 ms 604 KB Output is correct
28 Correct 4 ms 604 KB Output is correct
29 Correct 8 ms 604 KB Output is correct
30 Correct 5 ms 604 KB Output is correct
31 Correct 17 ms 604 KB Output is correct
32 Correct 6 ms 604 KB Output is correct
33 Correct 860 ms 3168 KB Output is correct
34 Correct 476 ms 2896 KB Output is correct
35 Execution timed out 1059 ms 4888 KB Time limit exceeded
36 Execution timed out 1026 ms 3708 KB Time limit exceeded
37 Correct 660 ms 3996 KB Output is correct
38 Execution timed out 1082 ms 5796 KB Time limit exceeded
39 Execution timed out 1075 ms 4620 KB Time limit exceeded
40 Correct 916 ms 4484 KB Output is correct
41 Execution timed out 1061 ms 7468 KB Time limit exceeded
42 Execution timed out 1039 ms 5268 KB Time limit exceeded
43 Execution timed out 1065 ms 5256 KB Time limit exceeded
44 Execution timed out 1042 ms 7512 KB Time limit exceeded
45 Execution timed out 1040 ms 6400 KB Time limit exceeded
46 Execution timed out 1061 ms 6292 KB Time limit exceeded
47 Execution timed out 1054 ms 9388 KB Time limit exceeded
48 Execution timed out 1038 ms 7276 KB Time limit exceeded
49 Execution timed out 1040 ms 7204 KB Time limit exceeded
50 Execution timed out 1030 ms 11300 KB Time limit exceeded
51 Incorrect 22 ms 2652 KB Output isn't correct
52 Incorrect 37 ms 2652 KB Output isn't correct
53 Execution timed out 1065 ms 4856 KB Time limit exceeded
54 Incorrect 24 ms 2648 KB Output isn't correct
55 Incorrect 32 ms 2784 KB Output isn't correct
56 Execution timed out 1032 ms 4968 KB Time limit exceeded
57 Incorrect 24 ms 2744 KB Output isn't correct
58 Incorrect 34 ms 2648 KB Output isn't correct
59 Execution timed out 1020 ms 5072 KB Time limit exceeded
60 Runtime error 20 ms 2220 KB Execution killed with signal 11
61 Runtime error 17 ms 2140 KB Execution killed with signal 11
62 Runtime error 17 ms 2396 KB Execution killed with signal 11
63 Runtime error 17 ms 2140 KB Execution killed with signal 11
64 Runtime error 17 ms 2136 KB Execution killed with signal 11
65 Runtime error 17 ms 2388 KB Execution killed with signal 11
66 Runtime error 17 ms 2132 KB Execution killed with signal 11
67 Runtime error 17 ms 2372 KB Execution killed with signal 11
68 Runtime error 17 ms 2396 KB Execution killed with signal 11
69 Runtime error 17 ms 2140 KB Execution killed with signal 11
70 Runtime error 22 ms 2376 KB Execution killed with signal 11
71 Runtime error 17 ms 2136 KB Execution killed with signal 11
72 Runtime error 19 ms 2196 KB Execution killed with signal 11
73 Runtime error 18 ms 2128 KB Execution killed with signal 11
74 Runtime error 22 ms 2388 KB Execution killed with signal 11
75 Runtime error 17 ms 2392 KB Execution killed with signal 11
76 Runtime error 17 ms 2140 KB Execution killed with signal 11
77 Runtime error 17 ms 2392 KB Execution killed with signal 11
78 Runtime error 17 ms 2140 KB Execution killed with signal 11
79 Runtime error 20 ms 2132 KB Execution killed with signal 11
80 Runtime error 17 ms 2048 KB Execution killed with signal 11
81 Runtime error 18 ms 2168 KB Execution killed with signal 11
82 Runtime error 17 ms 2136 KB Execution killed with signal 11
83 Runtime error 17 ms 2388 KB Execution killed with signal 11
84 Runtime error 17 ms 2116 KB Execution killed with signal 11
85 Runtime error 20 ms 2140 KB Execution killed with signal 11
86 Runtime error 19 ms 2124 KB Execution killed with signal 11
87 Runtime error 17 ms 2300 KB Execution killed with signal 11
88 Runtime error 17 ms 2396 KB Execution killed with signal 11
89 Runtime error 18 ms 2424 KB Execution killed with signal 11
90 Runtime error 17 ms 2132 KB Execution killed with signal 11
91 Runtime error 17 ms 2168 KB Execution killed with signal 11
92 Runtime error 17 ms 2140 KB Execution killed with signal 11