oj.uz

답안 #166687

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
166687 2019-12-03T13:25:03 Z Ort Tracks in the Snow (BOI13_tracks) C++11
100 / 100
 1619 ms 188148 KB 
#include<bits/stdc++.h>
#define MAX 4010

using namespace std;

struct state {
	int y, x, d;
	state(int y, int x, int d) {
		this->y = y;
		this->x = x;
		this->d = d;
	}
};

int n, m, s;
char mat[MAX][MAX];
bool visited[MAX][MAX];
deque<state> dq;
int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};

bool valid(int y, int x) {
	return y>=1 && y<=n && x>=1 && x<=m && !visited[y][x] && mat[y][x]!='.';
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin >> mat[i][j];
	dq.push_front(state(1,1,1));
	while(!dq.empty()) {
		state st = dq.front();
		dq.pop_front();
		visited[st.y][st.x] = true;
		s = max(s, st.d);
		for(int i=0;i<4;i++) {
			int nx = st.x+dx[i];
			int ny = st.y+dy[i];
			if(!valid(ny,nx)) continue;
			if(mat[st.y][st.x]==mat[ny][nx]) 
				dq.push_front(state(ny,nx,st.d));
			else
				dq.push_back(state(ny,nx,st.d+1));
		}
	}
	cout << s;
	return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 4648 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 21 ms 5084 KB Output is correct
5 Correct 13 ms 2740 KB Output is correct
6 Correct 3 ms 508 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 3 ms 888 KB Output is correct
9 Correct 3 ms 1144 KB Output is correct
10 Correct 7 ms 2424 KB Output is correct
11 Correct 7 ms 2296 KB Output is correct
12 Correct 14 ms 2840 KB Output is correct
13 Correct 8 ms 2660 KB Output is correct
14 Correct 8 ms 2776 KB Output is correct
15 Correct 26 ms 4600 KB Output is correct
16 Correct 57 ms 4600 KB Output is correct
17 Correct 20 ms 4504 KB Output is correct
18 Correct 19 ms 5028 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 30300 KB Output is correct
2 Correct 90 ms 11820 KB Output is correct
3 Correct 491 ms 47616 KB Output is correct
4 Correct 122 ms 18884 KB Output is correct
5 Correct 245 ms 32692 KB Output is correct
6 Correct 1568 ms 94788 KB Output is correct
7 Correct 35 ms 31820 KB Output is correct
8 Correct 34 ms 30328 KB Output is correct
9 Correct 5 ms 632 KB Output is correct
10 Correct 4 ms 376 KB Output is correct
11 Correct 34 ms 31224 KB Output is correct
12 Correct 4 ms 1528 KB Output is correct
13 Correct 94 ms 11800 KB Output is correct
14 Correct 54 ms 8436 KB Output is correct
15 Correct 37 ms 9208 KB Output is correct
16 Correct 41 ms 4344 KB Output is correct
17 Correct 224 ms 20256 KB Output is correct
18 Correct 142 ms 20048 KB Output is correct
19 Correct 121 ms 18868 KB Output is correct
20 Correct 120 ms 17544 KB Output is correct
21 Correct 337 ms 33892 KB Output is correct
22 Correct 262 ms 32768 KB Output is correct
23 Correct 421 ms 27728 KB Output is correct
24 Correct 250 ms 33868 KB Output is correct
25 Correct 550 ms 47428 KB Output is correct
26 Correct 1064 ms 188148 KB Output is correct
27 Correct 1415 ms 126684 KB Output is correct
28 Correct 1540 ms 94456 KB Output is correct
29 Correct 1619 ms 92508 KB Output is correct
30 Correct 1507 ms 111004 KB Output is correct
31 Correct 1197 ms 37372 KB Output is correct
32 Correct 1141 ms 117484 KB Output is correct