제출 #1096704

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

tracks

#include <iostream>
#include <cmath>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <tuple>
#include <numeric>
#include <map>
#include <bit>
#include <fstream>
#include <functional>
#include <array>
#include <chrono>
// #include<bits/stdc++.h>

/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/

using namespace std;

struct pair_hash {
    inline std::size_t operator()(const std::pair<int, int>& v) const {
        return v.first * 31 + v.second;
    }
};

struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
    // http://xorshift.di.unimi.it/splitmix64.c
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
}

size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
}
};

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/

#define rep(i, a, n) for(int i = a; i < n; ++i)
#define exists(s, e) (s.find(e) != s.end())
#define def_sort(s) (sort(s.begin(), s.end()))
#define def_reverse(s) (sort(s.rbegin(), s.rend()))
#define lsone(s) (s & -s)
#define endl '\n'

/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/

const long long INF = 1LL << 62;
using ll = long long;
using ull = unsigned long long;
typedef vector<int> vi;

/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/

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

const long long MOD = 1e9 + 7;
int rows, cols;

bool ok(int i, int j) {
    return (i >= 0 && j >= 0 && i < rows && j < cols);
}

/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/

ull read_int() {
    bool minus = false;
    ull result = 0;
    char ch;
    ch = getchar();
    while (true) {
        if (ch == '-') break;
        if (ch >= '0' && ch <= '9') break;
        ch = getchar();
    }
    if (ch == '-') minus = true;
    else result = ch - '0';
    while (true) {
        ch = getchar();
        if (ch < '0' || ch > '9') break;
        result = result * 10 + (ch - '0');
    }
    if (minus)
        return -result;
    else
        return result;
}

template <typename T>
T mod(T a, T b = 1) {
    T rez = a % b;
    if (rez < 0)
        rez += b;
    return rez;
}

void add(ll& a, ll b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/
char G[4010][4010];
int visited[4010][4010];
int res = 0;
void bfs()
{
    visited[0][0] = 1;
    deque<array<int,3>>pq;
    pq.push_front({1,0,0});
    while (!pq.empty())
    {
        array<int,3>tmp = pq.front();
        char c = G[tmp[1]][tmp[2]];
        res = max(res, tmp[0]);
        pq.pop_front();
        for(int z = 0; z < 4; ++z)
        {
            if(ok(tmp[1] + dx[z], tmp[2] + dy[z]) && !visited[tmp[1] + dx[z]][tmp[2] + dy[z]] && G[tmp[1] + dx[z]][tmp[2] + dy[z]]!= '.')
            {
                if(G[tmp[1] + dx[z]][tmp[2] + dy[z]] == c){
                    pq.push_front({tmp[0],tmp[1] + dx[z],tmp[2] + dy[z]});
                    visited[tmp[1] + dx[z]][tmp[2] + dy[z]] = 1;
                }
                else{
                    pq.push_back({tmp[0] + 1,tmp[1] + dx[z],tmp[2] + dy[z]});
                    visited[tmp[1] + dx[z]][tmp[2] + dy[z]] = 1;             
                }
            }
        }
    } 
    
}
void solve() {
    cin >> rows >> cols;
    memset(visited , 0, sizeof(visited));
    for(int i = 0; i < rows; ++i)
    {
        for(int j = 0; j < cols; ++j)
        cin >> G[i][j];
    }
    bfs();
    cout << res << endl;    
}

int main() {
    std::ios::sync_with_stdio(0), std::cin.tie(0);
#ifdef FIO
    // freopen("div7.in", "r", stdin);
    // freopen("div7.out", "w", stdout);
#endif
    // cout << setprecision(50);

int tc = 1;

#ifdef CF
    //cin >> tc;
#endif

while (tc--)
    solve();
cerr << "Time elapsed:" << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
return 0;
}

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