Submission #166687

#	Time	Username	Problem	Language	Result	Execution time	Memory
166687		Ort	Tracks in the Snow (BOI13_tracks)	C++11	100 / 100	1619 ms	188148 KiB

tracks

#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 / 30
• Subtask 2: 70 / 70