// to live is to die
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long int ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpl;
#define Clear(a, n) \
for (int i = 0; i <= n; i++) \
{ \
a[i] = 0; \
}
#define clearMat(a, n, m, d) \
for (int i = 0; i <= n; i++) \
{ \
for (int j = 0; j <= m; j++) \
a[i][j] = d; \
}
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define PB push_back
#define PF push_front
#define MP make_pair
#define F first
#define S second
#define rep(i, n) for (int i = 0; i < n; i++)
#define repe(i, j, n) for (int i = j; i < n; i++)
#define SQ(a) (a) * (a)
#define rep1(i, n) for (int i = 1; i <= n; i++)
#define Rrep(i, start, finish) for (int i = start; start >= finish; i--)
#define forn(i, Start, End, step) for (int i = Start; i <= End; i += step)
#define rforn(i, Start, End, step) for (int i = Start; i >= End; i -= step)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
// ll arr[SIZE];
/*
how to find n % mod ; n < 0?
x = (n+mod)%mod
if(x < 0) x += mod;
*/
void __print(int x)
{
cerr << x;
}
void __print(long x)
{
cerr << x;
}
void __print(long long x)
{
cerr << x;
}
void __print(unsigned x)
{
cerr << x;
}
void __print(unsigned long x)
{
cerr << x;
}
void __print(unsigned long long x)
{
cerr << x;
}
void __print(float x)
{
cerr << x;
}
void __print(double x)
{
cerr << x;
}
void __print(long double x)
{
cerr << x;
}
void __print(char x)
{
cerr << '\'' << x << '\'';
}
void __print(const char *x)
{
cerr << '\"' << x << '\"';
}
void __print(const string &x)
{
cerr << '\"' << x << '\"';
}
void __print(bool x)
{
cerr << (x ? "true" : "false");
}
template<typename T, typename V>
void __print(const pair<T, V> &x)
{
cerr << '{';
__print(x.first);
cerr << ',';
__print(x.second);
cerr << '}';
}
template<typename T>
void __print(const T &x)
{
int f = 0;
cerr << '{';
for (auto &i: x) cerr << (f++ ? "," : ""), __print(i);
cerr << "}";
}
void _print()
{
cerr << "]\n";
}
template <typename T, typename... V>
void _print(T t, V... v)
{
__print(t);
if (sizeof...(v)) cerr << ", ";
_print(v...);
}
#ifndef ONLINE_JUDGE
#define db(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define db(x...)
#endif
// order_of_key(k): # of elements less than k (which is the index of x = k)
// find_by_order(k); iterator of the k-th element
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T>
bool ckmin(T &a, const T &b)
{
return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T &a, const T &b)
{
return a < b ? a = b, 1 : 0;
}
template <typename T>
istream &operator>>(istream &in, vector<T> &a)
{
for (auto &x : a)
in >> x;
return in;
};
template <typename T>
ostream &operator<<(ostream &out, vector<T> &a)
{
for (auto &x : a)
out << x << ' ';
return out;
};
// priority_queue<data type , the container that would hold the values , greater<pair<int,int>>>
// greater means that we want the smallest value on top
// less means that we want the largest
// x ^ (n) mod m = ( (x mod m)^(n) ) mod m
char to_char(int num)
{
return (char)(num + '0');
}
ll const MAX = 1e18 + 1;
ll const oo = 1e18 + 1;
ll const INF = 1e9 + 10;
const ll MOD = 1e9 + 7;
ll const SIZE = 2e5 + 900;
const int LOG = 20;
template <typename T, typename T2>
void add(T &X, T2 Y)
{
X += Y;
if (X >= MOD)
{
X -= MOD;
}
}
template <typename T, typename T2>
T mult(T X, T2 Y)
{
return X * Y % MOD;
}
void setIO(string s)
{
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
// x & (-x) give me the minBit of x
// x & (x - 1) turns off rightmost bit
int dx[] = {1 , -1 , 0 , 0};
int dy[] = {0 , 0 , 1 , -1};
int N , M , depth[4001][4001] , answer = 1;
string snow[4000];
bool valid(int x, int y) {
return (x > -1 && x < N && y > -1 && y < M && snow[x][y] != '.');
}
void solve()
{
cin >> N >> M;
rep(i , N)
{
cin >> snow[i];
}
depth[0][0] = 1;
deque<pi>dq;
dq.PB({0 , 0});
while(dq.size())
{
pi cur = dq.front();
dq.pop_front();
answer = max(answer ,depth[cur.F][cur.S]);
for(int i = 0 ; i < 4 ; i ++)
{
int x = cur.F + dx[i] , y = cur.S + dy[i];
if(valid(x , y) && depth[x][y] == 0)
{
if(snow[x][y] == snow[cur.F][cur.S])
{
depth[x][y] = depth[cur.F][cur.S];
dq.push_front({x, y});
}else{
depth[x][y] = depth[cur.F][cur.S] + 1;
dq.PB({x , y});
}
}
}
}
cout << answer << "\n";
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
// setIO("");
int T = 1;
// cin >> T;
while (T--)
{
solve();
}
return 0;
}
/* stuff you should look for
* WRITE STUFF DOWN, ON PAPER
* BFS THEN DFS
* int overflow, array bounds
* special cases (n=1?)
* do sm th instead of nothing and stay organized
* DON'T GET STUCK ON ONE APPROACH
* (STUCK?)******** Try to simplify the problem(keeping in mind the main problem), ():
* 1- problem to subProblem
* 2- from simple to complex: start with a special
* problem and then try to update the solution for general case
* -(constraints - > solve it with none , one,two ... of them till you reach the given problem
-(no constraints - > try to give it some)
-how a special case may be incremented
* 3-Simplification by Assumptions
* REVERSE PROBLEM
* PROBLEM ABSTRACTION
* SMALL O BSERVATIONS MIGHT HELP ALOT
* WATCH OUT FOR TIME
* RETHINK YOUR IDEA,BETTER IDEA, APPROACH?
* CORRECT IDEA, NEED MORE OBSERVATIONS
* CORRECT APPROACH, WRONG IDEA
* WRONG APPROACH
* THINK CONCRETE THEN SYMBOL,
* having the solution for the first m state , can we solve it for m + 1 ?
* in many cases incremental thinking needs data sorting
*/
Compilation message
tracks.cpp: In function 'void setIO(std::string)':
tracks.cpp:203:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
203 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:204:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
204 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
3928 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
0 ms |
588 KB |
Output is correct |
| 4 |
Correct |
4 ms |
3672 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2140 KB |
Output is correct |
| 6 |
Correct |
0 ms |
604 KB |
Output is correct |
| 7 |
Correct |
0 ms |
604 KB |
Output is correct |
| 8 |
Correct |
1 ms |
860 KB |
Output is correct |
| 9 |
Correct |
1 ms |
860 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1628 KB |
Output is correct |
| 11 |
Correct |
2 ms |
1628 KB |
Output is correct |
| 12 |
Correct |
4 ms |
2140 KB |
Output is correct |
| 13 |
Correct |
2 ms |
2140 KB |
Output is correct |
| 14 |
Correct |
2 ms |
2124 KB |
Output is correct |
| 15 |
Correct |
7 ms |
3848 KB |
Output is correct |
| 16 |
Correct |
8 ms |
3932 KB |
Output is correct |
| 17 |
Correct |
6 ms |
3672 KB |
Output is correct |
| 18 |
Correct |
4 ms |
3676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
15960 KB |
Output is correct |
| 2 |
Correct |
27 ms |
12124 KB |
Output is correct |
| 3 |
Correct |
140 ms |
75276 KB |
Output is correct |
| 4 |
Correct |
48 ms |
29520 KB |
Output is correct |
| 5 |
Correct |
114 ms |
51536 KB |
Output is correct |
| 6 |
Correct |
390 ms |
109900 KB |
Output is correct |
| 7 |
Correct |
10 ms |
16732 KB |
Output is correct |
| 8 |
Correct |
7 ms |
15964 KB |
Output is correct |
| 9 |
Correct |
2 ms |
900 KB |
Output is correct |
| 10 |
Correct |
0 ms |
604 KB |
Output is correct |
| 11 |
Correct |
7 ms |
16476 KB |
Output is correct |
| 12 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 13 |
Correct |
27 ms |
11900 KB |
Output is correct |
| 14 |
Correct |
15 ms |
8024 KB |
Output is correct |
| 15 |
Correct |
15 ms |
10332 KB |
Output is correct |
| 16 |
Correct |
14 ms |
4956 KB |
Output is correct |
| 17 |
Correct |
68 ms |
25328 KB |
Output is correct |
| 18 |
Correct |
47 ms |
32336 KB |
Output is correct |
| 19 |
Correct |
53 ms |
29412 KB |
Output is correct |
| 20 |
Correct |
36 ms |
22612 KB |
Output is correct |
| 21 |
Correct |
93 ms |
50564 KB |
Output is correct |
| 22 |
Correct |
110 ms |
51540 KB |
Output is correct |
| 23 |
Correct |
141 ms |
42296 KB |
Output is correct |
| 24 |
Correct |
88 ms |
47440 KB |
Output is correct |
| 25 |
Correct |
195 ms |
96472 KB |
Output is correct |
| 26 |
Correct |
205 ms |
130652 KB |
Output is correct |
| 27 |
Correct |
273 ms |
122848 KB |
Output is correct |
| 28 |
Correct |
382 ms |
110056 KB |
Output is correct |
| 29 |
Correct |
402 ms |
108232 KB |
Output is correct |
| 30 |
Correct |
362 ms |
112380 KB |
Output is correct |
| 31 |
Correct |
311 ms |
72072 KB |
Output is correct |
| 32 |
Correct |
235 ms |
108268 KB |
Output is correct |
