Submission #880341

#	Time	Username	Problem	Language	Result	Execution time	Memory
880341		themaver1cks	Tracks in the Snow (BOI13_tracks)	C++11	100 / 100	734 ms	223240 KiB

tracks

/**
｡∠(*・ω･)っ  ⌒ 由 ~	((　,,・з・,,　))
 _Π_____。
/______/~＼
｜ 田田｜門｜
**/

#include <bits/stdc++.h>

using namespace std;

#define fori(i, l, r) for(int i = l; i < r; ++i)
#define forie(i, l, r) for (int i = l; i <= r; ++i)
#define ford(i, l, r) for (int i = l; i > r; --i)
#define forde(i, l, r) for (int i = l; i >= r; --i)
#define int long long
#define i_inf INT_MAX
#define inf LLONG_MAX
#define ii pair<int,int>
#define fi first
#define se second
#define gcd __gcd(x, y)
#define lcm(x,y) x * y/ gcd(x,y)
#define pb push_back
#define eb emplace_back
#define sz size
#define all(x) begin(x), end(x)
#define fastio ios_base::sync_with_stdio(0); cin.tie(nullptr);
#define el "\n"
#define sp " "
//
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
// var declare
const int maxn = 4e3 + 3;
int n, m;
int ans = 0;
// ds declare
char a[maxn][maxn];
//
bool check(int x, int y)
{
    return (x > 0 && y > 0 && x <= m && y <= n && a[x][y] != '.');
}
//
void bfs0_1()
{
    deque <ii> dq;
    vector <vector<int>> d(m+1, vector<int>(n+1, 0));
    d[1][1] = 1;
    dq.push_front({1, 1});
    while (dq.sz())
    {
        auto [x, y] = dq.front();
        dq.pop_front();
        ans = max(ans, d[x][y]);
        fori(z, 0, 4)
        {
            int x1 = x + dr[z], y1 = y + dc[z];
            if (check(x1, y1) && d[x1][y1] == 0)
            {
                if (a[x][y] == a[x1][y1])
                {
                    d[x1][y1] = d[x][y];
                    dq.push_front({x1, y1});
                }
                else
                {
                    d[x1][y1] = d[x][y] + 1;
                    dq.push_back({x1, y1});
                }
            }
        }
    }
}
//
void solve()
{
    cin >> m >> n;
    forie(i, 1, m)
        forie(j, 1, n) cin >> a[i][j];
    bfs0_1();
    cout << ans;
}
//
void multi_test()
{
	int t;
	cin >> t;
	while (t--) solve();
}
//
int32_t main()
{
	fastio;
	solve();
	return 0;
}

/**
5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF
**/

Compilation message (stderr)

tracks.cpp: In function 'void bfs0_1()':
tracks.cpp:54:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |         auto [x, y] = dq.front();
      |              ^

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