This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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];
char curr[2] = {'F','R'};
int visited[4010][4010];
int res = 0;
void bfs(int x, int y, char c,int k)
{
visited[x][y] = k;
priority_queue<array<int,3>>pq;
pq.push({k,x,y});
while (!pq.empty())
{
array<int,3>tmp = pq.top();
res = max(res, tmp[0]);
pq.pop();
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({k,tmp[1] + dx[z],tmp[2] + dy[z]});
visited[tmp[1] + dx[z]][tmp[2] + dy[z]] = tmp[0];
}
else{
pq.push({k + 1,tmp[1] + dx[z],tmp[2] + dy[z]});
visited[tmp[1] + dx[z]][tmp[2] + dy[z]] = tmp[0] + 1;
}
}
}
}
}
void solve() {
cin >> rows >> cols;
int cnt = 0;
for(int i = 0; i < rows; ++i)
{
for(int j = 0; j < cols; ++j)
cin >> G[i][j];
}
bfs(0,0,G[0][0],1);
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;
}
Compilation message (stderr)
tracks.cpp: In function 'void solve()':
tracks.cpp:151:9: warning: unused variable 'cnt' [-Wunused-variable]
151 | int cnt = 0;
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |