oj.uz

답안 #82159

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
82159 2018-10-29T10:11:31 Z heon Pohlepko (COCI16_pohlepko) C++11
80 / 80
 26 ms 19152 KB 
#include<bits/stdc++.h>

using namespace std;

const int dx[] = {1, 0};
const int dy[] = {0, 1};

bool bio[2002][2002];

int main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
  
	int n,m;
	cin >> n >> m;
	vector <string> s(n);
	for(int i = 0; i < n; i++) cin >> s[i];
	vector <pair<int,int>> q;
	q.push_back(make_pair(0,0));
	bio[0][0] = 1;
	string sol;
	while(!q.empty()){
		cout << s[q.back().first][q.back().second];
		vector <pair<int,int>> next;
		char mn = 'z';
		for(auto x : q){
			for(int i = 0; i < 2; i++){
				int nx = dx[i] + x.first;
				int ny = dy[i] + x.second;
				if(nx >= n || ny >= m) continue;
				mn = min(mn, s[nx][ny]);
			}
		}
		for(auto x : q){
			for(int i = 0; i < 2; i++){
				int nx = dx[i] + x.first;
				int ny = dy[i] + x.second;
				if(nx >= n || ny >= m || s[nx][ny] != mn || bio[nx][ny]) continue;
				next.push_back(make_pair(nx,ny));
				bio[nx][ny] = 1;
			}
		}
		q = next;
	}
}

Subtask #1
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 1492 KB Output is correct
3 Correct 2 ms 1492 KB Output is correct
4 Correct 2 ms 1492 KB Output is correct
5 Correct 3 ms 1492 KB Output is correct
6 Correct 4 ms 1712 KB Output is correct
7 Correct 9 ms 6232 KB Output is correct
8 Correct 16 ms 14328 KB Output is correct
9 Correct 2 ms 14328 KB Output is correct
10 Correct 3 ms 14328 KB Output is correct
11 Correct 3 ms 14328 KB Output is correct
12 Correct 6 ms 14328 KB Output is correct
13 Correct 9 ms 14328 KB Output is correct
14 Correct 17 ms 19152 KB Output is correct
15 Correct 3 ms 19152 KB Output is correct
16 Correct 26 ms 19152 KB Output is correct