Submission #415969

#	Time	Username	Problem	Language	Result	Execution time	Memory
415969		nkato	Tracks in the Snow (BOI13_tracks)	C++17	2.19 / 100	2072 ms	179096 KiB

tracks

#include <bits/stdc++.h>

#define ll long long
#define vi vector<int>
#define pi pair<int, int>
#define se second
#define fi first
#define vt vector
#define pb push_back
#define nl endl

#define dbg(...) " [" << #__VA_ARGS__": " << (__VA_ARGS__) << "] "
#define all(v) v.begin(), v.end()
#define FORN(a, b, i) for(int i = (a); i < (b); i++)
#define FORE(a, b, i) for(int i = (a); i <= (b); i++)
#define FOR(a, i) for(int i = 0; i < (a); i++)
#define trav(x, a) for (auto& a : x)

using namespace std;

void setIO(string name) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if (name.empty()) return;
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}


const int nax = 4000;
int b[nax][nax], dep[nax][nax];
int del[4] = {-1, 1, 0, 0};
int n, m;
bool inside(int x, int y) {
	return !(x >= n || x < 0 || y >= m || y < 0 || b[x][y] == 0 || dep[x][y] != -1);
}

int main() {


	memset(dep, -1, sizeof(dep));

	cin >> n >> m;
	FOR(n, i) FOR(m, j) {
		char c; cin >> c;
		b[i][j] = (c == '.' ? (c == 'F' ? 1 : 2) : 0);
	}

	deque<pair<int, int>> d;
	dep[0][0] = 1;
	d.push_back({0, 0});
	int ans = 0;
	while(!d.empty()) {
		pi u = d.front();
		d.pop_front();
		ans = dep[u.fi][u.se];
		for(int i = 0; i < 4; i++) {
			for(int j = 3; j >= 0; j--) {
				if (inside(u.fi+del[i], u.se+del[j])) {
					pi v = {u.fi+del[i], u.se+del[j]};
					if (b[v.fi][v.se] == b[u.fi][u.se]) {
						dep[v.fi][v.se] = dep[u.fi][u.se];
						d.push_front(v);
					} else {
						dep[v.fi][v.se] = dep[u.fi][u.se]+1;
						d.push_back(v);
					}
				}
			}
		}
	}
	cout << ans << endl;
    
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'void setIO(std::string)':
tracks.cpp:24:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:25:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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