Submission #46595

#	Time	Username	Problem	Language	Result	Execution time	Memory
46595		Bruteforceman	Tracks in the Snow (BOI13_tracks)	C++11	100 / 100	949 ms	316896 KiB

tracks

#include "bits/stdc++.h"
using namespace std;
char a[4001][4001];
int d[4001][4001];
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
int N, M;
typedef pair <int, int> pii;
const int inf = 1e9;

bool inside(int x, int y) {
	return (0 <= x && x < N) && (0 <= y && y < M);
}

int main(int argc, char const *argv[])
{
	scanf("%d %d", &N, &M);
	for(int i = 0; i < N; i++) {
		scanf("%s", a[i]);
	}
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < M; j++) {
			d[i][j] = inf;
		}
	}
	deque <pii> Q;
	Q.push_front(pii(N - 1, M - 1));
	d[N - 1][M - 1] = 0;

	while(!Q.empty()) {
		pii c = Q.front();
		Q.pop_front();
		for(int i = 0; i < 4; i++) {
			int p = c.first + dx[i];
			int q = c.second + dy[i];
			if(inside(p, q) && a[p][q] != '.') {
				int w = (a[c.first][c.second] != a[p][q]);
				if(d[p][q] > w + d[c.first][c.second]) {
					d[p][q] = w + d[c.first][c.second];
					if(w) Q.push_back(pii(p, q));
					else Q.push_front(pii(p, q));
				} 
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < M; j++) {
			if(a[i][j] != '.') {
				ans = max(ans, d[i][j]);
			}
		}
	}
	printf("%d\n", ans + 1);
	return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main(int, const char**)':
tracks.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~
tracks.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", a[i]);
   ~~~~~^~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70