제출 #371124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
371124		plourde27	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1625 ms	307188 KiB

tracks

#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <map>
#include <fstream>
#include <bitset>
#include <unordered_map>
#include <stack>
#include <list>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef map<int, int> mii;
typedef map<int, string> mis;
typedef map<string, int> msi;
typedef set<int> si;
typedef set<ll> sl;
typedef map<ll, ll> mll;
typedef queue<int> qi;
typedef queue<ii> qii;
typedef vector<string> vs;
typedef pair<ll, ll> iil;
typedef priority_queue<int> pqi;
typedef priority_queue<ii> pqii;
typedef priority_queue<ll> pqil;
typedef priority_queue<iil> pqiil;
typedef vector<iil> viil;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int, ii> iii;
typedef pair<iil, ll> iiil;
typedef vector<pair<pair<int,int>,int> > viii;
typedef vector<pair<pair<ll,ll>,ll> > viiil;
typedef vector<vl> vvl;

#define pb push_back
#define mp make_pair
#define rep(i, n) for (int i = 0 ; i < n ; i++)
#define rrep(i, m, n) for (int i = m ; i < n ; i++)
#define per(i, n) for (int i = n - 1 ; i >= 0 ; i--)
#define perr(i, m, n) for (int i = n - 1 ; i >= m ; i--)
#define INF 2000000000

ll MOD = 1000000007;

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

int vis[4005][4005];
int dist[4005][4005];

void solve() {
    int n, m;
    cin >> n >> m;
    
    int mat[n][m];
    
    rep(i, n) {
        string s;
        cin >> s;
        rep(j, m) {
            mat[i][j] = s[j];
        }
    }
    
    deque<pair<pair<int, int>, int>> q;
    
    q.push_back({{0, 0}, 0});
    
    rep(i, n) {
        rep(j, m) {
            dist[i][j] = INF;
        }
    }
    
    while (q.size()) {
        pair<pair<int, int>, int> inf = q.front();
        q.pop_front();
        
        int x = inf.first.first;
        int y = inf.first.second;
        int d = inf.second;
        
        dist[x][y] = min(dist[x][y], d);
        
        
        vis[x][y] = true;
        
        rep(k, 4) {
            int xx = x + dx[k];
            int yy = y + dy[k];
            if (xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
            if (mat[xx][yy] == '.') continue;
            
            if (mat[xx][yy] == mat[x][y]) {
                if (d < dist[xx][yy]) {
                    q.push_front({{xx, yy}, d});
                }
            }
            else {
                if (d+1 < dist[xx][yy]) {
                    q.push_back({{xx, yy}, d+1});
                }
            }
        }
        
        
    }
    
    int ans = 0;
    
    rep(i, n) {
        rep(j, m) {
            if (dist[i][j] != INF) {
                //cout << dist[i][j] << " ";
                ans = max(ans, dist[i][j]);
            }
            else {
                //cout << 0 << " ";
            }
        }
        //cout << endl;
    }
    
    cout << ans+1 << endl;
}

void querySolve() {
    int t;
    cin >> t;
    for (int i = 0 ; i < t ; i++) {
        solve();
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    solve();
    //querySolve();
}

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