Submission #136618

#	Time	Username	Problem	Language	Result	Execution time	Memory
136618		Lawliet	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1668 ms	144940 KiB

tracks

#include <bits/stdc++.h>

#define MAX 4010

using namespace std;

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

int n, m;
int maxDist;

int dist[MAX][MAX];

bool marc[MAX][MAX];

char v[MAX][MAX];

deque<int> dq;

void add(int i, int j, int d, bool t = false)
{
	dist[i][j] = d;
	marc[i][j] = true;

	maxDist = max(maxDist , d);

	if(t)
	{
		dq.push_front(j);
		dq.push_front(i);
	}
	else
	{
		dq.push_back(i);
		dq.push_back(j);
	}
}

bool check(int i, int j)
{
	if(i <= 0 || j <= 0) return false;
	if(i > n || j > m) return false;
	if(v[i][j] == '.') return false;

	return !marc[i][j];
}

void BFS()
{
	add(1 , 1 , 1);

	while(!dq.empty())
	{
		int curX = dq.front(); dq.pop_front();
		int curY = dq.front(); dq.pop_front();

		for(int g = 0 ; g < 4 ; g++)
		{
			int dX = curX + dx[g];
			int dY = curY + dy[g];
			int d = dist[curX][curY];

			if(!check(dX , dY)) continue;

			if(v[dX][dY] != v[curX][curY]) add(dX , dY , d + 1);
			else add(dX , dY , d , true);
		}
	}
}

int main()
{
	scanf("%d %d",&n,&m);

	for(int g = 1 ; g <= n ; g++)
		for(int h = 1 ; h <= m ; h++)
			scanf(" %c",&v[g][h]);

	BFS();

	printf("%d\n",maxDist);
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:74: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:78:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c",&v[g][h]);
    ~~~~~^~~~~~~~~~~~~~~~

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