제출 #445988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
445988		minhi1	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	803 ms	131048 KiB

tracks

#include <bits/stdc++.h>
#define forw(i,a,b) for (int i = (a); i <= (b); i++)
#define ford(i,a,b) for (int i = (a); i >= (b); i--)
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define ff first
#define ss second
#define ALL(v) (v).begin(), (v).end()
#define nl '\n'
using namespace std;
template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        }
        return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        }
        return false;
    }
/*                  AHIHI                   */
#define MAX  4010
typedef long long ll;
typedef pair<int, int> pii;

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

int n,m,res,d[MAX][MAX];
char a[MAX][MAX];

bool ins(int u,int v)
{
    return min(u,v) >= 1 && u <= n && v <= m;
}

void bfs()
{
    deque<pii> q;
    q.push_back({1,1});
    d[1][1] = 1;

    while (q.size()) {
        pii c = q.front(); q.pop_front();
        maximize(res, d[c.ff][c.ss]);

        rep(i,0,4) {
            int u = c.ff + dx[i], v = c.ss + dy[i];
            if (ins(u,v) && d[u][v] == 0 && a[u][v]!='.') {
                if (a[u][v] == a[c.ff][c.ss]) {
                    d[u][v] = d[c.ff][c.ss];
                    q.push_front({u,v});
                }
                else {
                    d[u][v] = d[c.ff][c.ss] + 1;
                    q.push_back({u,v});
                }
            }
        }
    }
}

void solve(int tc)
{
    cin >> n >> m;
    forw(i,1,n) forw(j,1,m) cin >> a[i][j];
    bfs();
    cout << res << nl;
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0);
//    string name = "HT";
//    freopen((name + ".inp").c_str(),"r",stdin);
//    freopen((name + ".out").c_str(),"w",stdout);
    int T = 1;
//    cin >> T;
    forw(i,1,T) solve(i);
    return 0;
}

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