Submission #545757

#	Time	Username	Problem	Language	Result	Execution time	Memory
545757		AA_Surely	Tracks in the Snow (BOI13_tracks)	C++17	75.31 / 100	943 ms	134172 KiB

tracks

#include <bits/stdc++.h>

#define FOR(i,x,n) 	for(int i=x; i<n; i++)
#define F0R(i,n) 	FOR(i,0,n)
#define ROF(i,x,n) 	for(int i=n-1; i>=x; i--)
#define R0F(i,n) 	ROF(i,0,n)

#define WTF 		cout << "WTF" << endl

#define IOS 		ios::sync_with_stdio(false); cin.tie(0)
#define F 			first
#define S	 		second
#define pb 			push_back

#define ALL(x) 		x.begin(), x.end()
#define RALL(x) 	x.rbegin(), x.rend()

using namespace std;
typedef long long 		LL;

typedef pair<int, int> 	PII;
typedef pair<LL, LL> 	PLL;

typedef vector<int> 	VI;
typedef vector<LL> 		VLL;
typedef vector<PII> 	VPII;
typedef vector<PLL> 	VPLL;

const int MAXN = 4000 + 7;
const int ALPHA = 27;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int LOG = 22;

int n, m;
int dist[MAXN][MAXN];
char grid[MAXN][MAXN];
deque<PII> keep;

int xm[4] = {1, 0, 0,-1};
int ym[4] = {0,-1, 1, 0};

inline bool safe(int x, int y) {
    if (x < 0 || x >= n) return 0;
    if (y < 0 || y >= m) return 0;
    return 1;
}

int main() {
    IOS;
    
    cin >> n >> m;
    F0R(i, n) F0R(j, m) cin >> grid[i][j];

    F0R(i, n) F0R(j, n) dist[i][j] = INF;
    dist[0][0] = 0;
    keep.push_front({0, 0});

    while(!keep.empty()) {
        int x = keep.front().F, y = keep.front().S;
        keep.pop_front();

        F0R(i, 4) {
            int nx = x + xm[i], ny = y + ym[i];
            if (safe(nx, ny)) {
                if (grid[nx][ny] == '.') continue;
                if (grid[nx][ny] == grid[x][y] && dist[nx][ny] > dist[x][y]) {
                    keep.push_front({nx, ny});
                    dist[nx][ny] = dist[x][y];
                }

                if (grid[nx][ny] != grid[x][y] && dist[nx][ny] > dist[x][y] + 1) {
                    keep.push_back({nx, ny});
                    dist[nx][ny] = dist[x][y] + 1;
                }
            }
        }
    }

    /*F0R(i, n) {
        F0R(j, m) cout << dist[i][j] << ' ';
        cout << endl;
    }*/

    int ans = 0;
    F0R(i, n) F0R(j, m) if (dist[i][j] != INF) ans = max(ans, dist[i][j]);
    cout << ans + 1;
}

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