//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimize("unroll-loops")
#include "bits/stdc++.h"
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define node pair<int,int>
#define ordered_set tree<node, null_type,less<node>, rb_tree_tag,tree_order_statistics_node_update>
//order_of_key (k) : Number of items strictly smaller than k
//find_by_order(k) : K-th element in a set (counting from zero)
*/
#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define ff first
#define endl '\n'
#define ss second
#define int long long
#define pb push_back
#define mp make_pair
#define fr(i, s, e) for(int i = s; i < e; i++)
#define rfr(i, s, e) for(int i = s; i >= e; i--)
#define geta(a, n) for(int i = 0; i < n; i++) cin >> a[i];
#define pii pair<int,int>
#define vi vector<int>
#define mii map<int,int>
#define pqb priority_queue<int>
#define pqs priority_queue<int,vi,greater<int> >
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define inf 1e18
#define ps(x,y) fixed<<setprecision(y)<<x
#define mk(arr,n,type) type *arr=new type[n];
#define all(x) x.begin(),x.end()
#define MOD 1000000007
using namespace std;
using ll = long long;
int dx[] = { -1, 1, 0, 0}; int dy[] = {0, 0, 1, -1};
// int dx[]={2,2,-2,-2,1,1,-1,-1}; int dy[]={1,-1,1,-1,2,-2,2,-2};
/*------------------------------UNORDERED MAP HASH --------------------------------------------*/
//To make unordered_map unhackable
// use it as unordered_map<int,int,custom_hash> mapp;
/*
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);
}
};
*/
/*------------------------------END--------------------------------------------*/
inline int powMod(int a, int b) { int x = 1; while (b > 0) { if (b & 1) x = (x * a) % MOD; a = (a * a) % MOD; b >>= 1; } return x; }
inline int multiply(int x, int y) { return ((x % MOD) * (y % MOD)) % MOD; }
inline int divide(int x, int y) { return ((x % MOD) * powMod(y % MOD, MOD - 2)) % MOD; }
inline int ceil(int a, int b) { return (a + b - 1) / b; }
int gcd (int a, int b) { while (b) { a %= b; swap(a, b); } return a; }
int lcm (int a, int b) { return a / gcd(a, b) * b; }
int inverseMod(int a, int m) { a = a % m; for (ll x = 1; x < m; x++) if ((a * x) % m == 1) return x; return -1; }
#ifdef GAURAVDEBUG
#include "C:\Users\gengi\OneDrive\Documents\debug.cpp"
#else
#define debug(...) ""
#endif
template<int D, typename T> struct vec : public vector < vec < D - 1, T >> { static_assert(D >= 1, "Vector dimension must be greater than zero!"); template<typename... Args> vec(int n = 0, Args... args) : vector < vec < D - 1, T >> (n, vec < D - 1, T > (args...)) { } }; template<typename T> struct vec<1, T> : public vector<T> { vec(int n = 0, T val = T()) : vector<T>(n, val) { }};
/*
5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF
*/
int h,w;
vector<string> mat;
void solve() {
cin >> h >> w;
mat.resize(h);
for (int i = 0; i < h; i++) {
cin >> mat[i];
}
deque<pii> dq;
dq.push_front({0, 0});
int ans = 0;
vector<vector<int>> dis(h, vector<int>(w, INT_MIN));
dis[0][0] = 1;
auto inside = [&](int x, int y)->bool{
return x >= 0 and y >= 0 and x < h and y < w and mat[x][y] != '.';
};
vector<vector<bool>> vis(h, vector<bool>(w, false));
debug(mat);
while (!dq.empty()) {
auto p = dq.front();
dq.pop_front();
int i = p.ff; int j = p.ss;
if (vis[i][j]) continue;
vis[i][j] = true;
ans=max(ans,dis[i][j]);
// cout<<"i "<<" "<<j<<" "<<endl;
for (int k = 0; k < 4; k++) {
int x = i + dx[k];
int y = j + dy[k];
if (inside(x, y) and !vis[x][y]) {
if (mat[x][y] == mat[i][j])
{
dq.push_front({x,y});
dis[x][y]=dis[i][j];
}
else
{
dq.push_back({x,y});
dis[x][y]=dis[i][j] + 1;
}
}
}
}
cout<<ans;
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}
Compilation message
tracks.cpp: In function 'void solve()':
tracks.cpp:79:20: warning: statement has no effect [-Wunused-value]
79 | #define debug(...) ""
| ^~
tracks.cpp:108:5: note: in expansion of macro 'debug'
108 | debug(mat);
| ^~~~~
tracks.cpp: In function 'int32_t main()':
tracks.cpp:148:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
148 | freopen("error.txt", "w", stderr);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
3040 KB |
Output is correct |
| 2 |
Correct |
1 ms |
324 KB |
Output is correct |
| 3 |
Correct |
1 ms |
324 KB |
Output is correct |
| 4 |
Correct |
9 ms |
2576 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1108 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
2 ms |
980 KB |
Output is correct |
| 11 |
Correct |
3 ms |
852 KB |
Output is correct |
| 12 |
Correct |
7 ms |
1352 KB |
Output is correct |
| 13 |
Correct |
2 ms |
1108 KB |
Output is correct |
| 14 |
Correct |
3 ms |
1108 KB |
Output is correct |
| 15 |
Correct |
14 ms |
2900 KB |
Output is correct |
| 16 |
Correct |
16 ms |
2996 KB |
Output is correct |
| 17 |
Correct |
10 ms |
2772 KB |
Output is correct |
| 18 |
Correct |
9 ms |
2632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 2 |
Correct |
47 ms |
16116 KB |
Output is correct |
| 3 |
Correct |
249 ms |
161264 KB |
Output is correct |
| 4 |
Correct |
64 ms |
37972 KB |
Output is correct |
| 5 |
Correct |
133 ms |
90740 KB |
Output is correct |
| 6 |
Correct |
971 ms |
210708 KB |
Output is correct |
| 7 |
Correct |
3 ms |
1236 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 9 |
Correct |
2 ms |
980 KB |
Output is correct |
| 10 |
Correct |
1 ms |
596 KB |
Output is correct |
| 11 |
Correct |
2 ms |
1264 KB |
Output is correct |
| 12 |
Correct |
1 ms |
468 KB |
Output is correct |
| 13 |
Correct |
48 ms |
16024 KB |
Output is correct |
| 14 |
Correct |
25 ms |
9432 KB |
Output is correct |
| 15 |
Correct |
15 ms |
10408 KB |
Output is correct |
| 16 |
Correct |
29 ms |
6824 KB |
Output is correct |
| 17 |
Correct |
125 ms |
41128 KB |
Output is correct |
| 18 |
Correct |
67 ms |
40492 KB |
Output is correct |
| 19 |
Correct |
61 ms |
37968 KB |
Output is correct |
| 20 |
Correct |
59 ms |
34872 KB |
Output is correct |
| 21 |
Correct |
150 ms |
93896 KB |
Output is correct |
| 22 |
Correct |
120 ms |
90644 KB |
Output is correct |
| 23 |
Correct |
226 ms |
78252 KB |
Output is correct |
| 24 |
Correct |
148 ms |
91700 KB |
Output is correct |
| 25 |
Correct |
342 ms |
161200 KB |
Output is correct |
| 26 |
Correct |
646 ms |
322620 KB |
Output is correct |
| 27 |
Correct |
899 ms |
229652 KB |
Output is correct |
| 28 |
Correct |
1000 ms |
210708 KB |
Output is correct |
| 29 |
Correct |
1088 ms |
204016 KB |
Output is correct |
| 30 |
Correct |
919 ms |
214676 KB |
Output is correct |
| 31 |
Correct |
832 ms |
104996 KB |
Output is correct |
| 32 |
Correct |
778 ms |
216512 KB |
Output is correct |
