////------------> FLS.
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using ld = long double;
#define int long long
#define double long double
#define endl '\n'
#define FLS ios_base::sync_with_stdio(false);cin.tie(0); cout.tie(0);
#define vin(a) for(auto&XX:a)cin>>XX;//idk y but it restricts my thought process at times
#define vout(v) for (auto XX: v)cout<<XX<<' ';cout<<endl;
#define vvin(a) for(auto& b : a) {for(auto& x : b) cin>>x;}
#define vvout(a) for(auto& b: a) {for(auto& x : b) {cout<<x<<" ";}cout<<endl;}
#define meh {cout<<"NO"<<endl;return;}
#define yay {cout<<"YES"<<endl;return;}
#define IMmeh {cout<<"NO"<<endl;continue;}
#define IMyay {cout<<"YES"<<endl;continue;}
//=======================================================------------------------------------------------------
void print(int t) {cout << t;}
void print(string t) {cout << t;}
void print(char t) {cout << t;}
void print(double t) {cout << t;}
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(pair <T, V> p) {cout << "{"; print(p.first); cout << ","; print(p.second); cout << "}";}
template <class T> void print(vector <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]\n";}
template <class T> void print(set <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]\n";}
template <class T> void print(multiset <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]\n";}
template <class T, class V> void print(map <T, V> v) {cout << "[ "; for (auto i : v) {print(i); cout << " ";} cout << "]\n";}
//=======================================================------------------------------------------------------
// #define pow2(x) (1ll<<(x))
template <typename T, typename U> T cdiv(T x, U y) {assert(y!=0);return (x > 0 ? (x + y - 1) / y : x / y);}
template <typename T, typename U> T fdiv(T x, U y) {assert(y!=0);return (x > 0 ? x / y : (x - y + 1) / y);}
template <typename T> int sgn(T val) {return (T(0) < val) - (val < T(0));} //sgn(x) gives -1/0/1
//returns integer, only works if a is a guarantee perfect square
long long sqroot(long long a){long long b = (long long) sqrtl(a);if ((b + 1) * (b + 1) == a){b++;}return b;}
constexpr ll inf = 1E18;
//(raise(a,b) = a^b) [a,b > 0].
long long raise(long long a, long long b) {long long res = 1;for(int i = 0; i<b; i++) {if(inf/res < a) return 0;res *= a;}return res;}
bool isSquare(int n) {int r = sqrtl(1.0L * n);return r*r == n;}
//=======================================================----------------------------------
const int MAX = 200007; //2*10^5 + 7
const int mod = 1000000007; //1e9+7, comment it out if u want to use the other MOD
// // const int MOD = 998244353;
// const double EPS=1E-9;
// const int MAXN = 10000010; //1e7+10
//----------------
int dx[4]{1, -1, 0, 0};
int dy[4]{0, 0, 1, -1};
vector<vector<int>> depth(4000, vector<int>(4000));
vector<string> snow(4000);
void solve() {
int n, m; cin >> n >> m;
for(int i = 0; i < n; i++) cin >> snow[i];
auto inside = [&](int x, int y) -> bool {
return (x >= 0 && x < n && y >= 0 && y < m && snow[x][y] != '.');
};
int ans = 1;
deque<pair<int, int>> dq;
dq.push_back({0, 0}); depth[0][0] = 1;
while(dq.empty() == false) {
pair<int, int> node_coords = dq.front();
dq.pop_front();
ans = max(ans, depth[node_coords.first][node_coords.second]);
for(int direction = 0; direction < 4; direction++) {
int x_new = node_coords.first + dx[direction]; int y_new = node_coords.second + dy[direction];
if(inside(x_new, y_new) == true) {
if(depth[x_new][y_new] != 0) {
// if depth[x][y] has already been updated, that means the node {x,y}..
//.. has already been reached by a shorter route.
// so dont update depth[x][y]; we want to retain the shortest value for depth of a node.
} else {
if(snow[node_coords.first][node_coords.second] == snow[x_new][y_new]) {
// same animal? -> weight zero. keep the depth same and push_front.
depth[x_new][y_new] = depth[node_coords.first][node_coords.second];
dq.push_front({x_new, y_new});
} else {
// different animal? -> weight one. increment the depth, and push_back
depth[x_new][y_new] = depth[node_coords.first][node_coords.second] + 1;
dq.push_back({x_new, y_new});
}
}
}
}
}
cout << ans << endl;
// each depth level represents an animal
// the deepest level is the first animal that had crossed the meadow
// the least level (1) is the last (recentmost) animal that had crossed the meadow.
// cout<<"===="<<endl;
}
/*ngu, lesgo*/
int32_t main() {
FLS
//cout<<fixed<<setprecision(20)<<x; //-> for printing a double 'x'.
// freopen("", "r", stdin);
// freopen("", "w", stdout);
int TT=1;
// cin>>TT; //comment out this line if only 1 test case is needed
while(TT--) {
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
126556 KB |
Output is correct |
| 2 |
Correct |
75 ms |
125776 KB |
Output is correct |
| 3 |
Correct |
65 ms |
125892 KB |
Output is correct |
| 4 |
Correct |
68 ms |
126568 KB |
Output is correct |
| 5 |
Correct |
67 ms |
126108 KB |
Output is correct |
| 6 |
Correct |
68 ms |
125872 KB |
Output is correct |
| 7 |
Correct |
68 ms |
125888 KB |
Output is correct |
| 8 |
Correct |
66 ms |
125780 KB |
Output is correct |
| 9 |
Correct |
67 ms |
125988 KB |
Output is correct |
| 10 |
Correct |
67 ms |
125964 KB |
Output is correct |
| 11 |
Correct |
74 ms |
126032 KB |
Output is correct |
| 12 |
Correct |
70 ms |
126172 KB |
Output is correct |
| 13 |
Correct |
67 ms |
126132 KB |
Output is correct |
| 14 |
Correct |
71 ms |
125988 KB |
Output is correct |
| 15 |
Correct |
78 ms |
126524 KB |
Output is correct |
| 16 |
Correct |
79 ms |
126584 KB |
Output is correct |
| 17 |
Correct |
72 ms |
126292 KB |
Output is correct |
| 18 |
Correct |
71 ms |
126544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
125812 KB |
Output is correct |
| 2 |
Correct |
92 ms |
129108 KB |
Output is correct |
| 3 |
Correct |
198 ms |
159272 KB |
Output is correct |
| 4 |
Correct |
116 ms |
133460 KB |
Output is correct |
| 5 |
Correct |
169 ms |
144272 KB |
Output is correct |
| 6 |
Correct |
642 ms |
186604 KB |
Output is correct |
| 7 |
Correct |
68 ms |
126024 KB |
Output is correct |
| 8 |
Correct |
68 ms |
125956 KB |
Output is correct |
| 9 |
Correct |
66 ms |
125912 KB |
Output is correct |
| 10 |
Correct |
75 ms |
125908 KB |
Output is correct |
| 11 |
Correct |
68 ms |
125776 KB |
Output is correct |
| 12 |
Correct |
67 ms |
125776 KB |
Output is correct |
| 13 |
Correct |
92 ms |
128944 KB |
Output is correct |
| 14 |
Correct |
82 ms |
127800 KB |
Output is correct |
| 15 |
Correct |
82 ms |
127828 KB |
Output is correct |
| 16 |
Correct |
79 ms |
127272 KB |
Output is correct |
| 17 |
Correct |
131 ms |
134244 KB |
Output is correct |
| 18 |
Correct |
124 ms |
134360 KB |
Output is correct |
| 19 |
Correct |
112 ms |
133712 KB |
Output is correct |
| 20 |
Correct |
99 ms |
132956 KB |
Output is correct |
| 21 |
Correct |
144 ms |
144976 KB |
Output is correct |
| 22 |
Correct |
165 ms |
144464 KB |
Output is correct |
| 23 |
Correct |
197 ms |
141972 KB |
Output is correct |
| 24 |
Correct |
144 ms |
144612 KB |
Output is correct |
| 25 |
Correct |
529 ms |
159316 KB |
Output is correct |
| 26 |
Correct |
379 ms |
252424 KB |
Output is correct |
| 27 |
Correct |
452 ms |
212292 KB |
Output is correct |
| 28 |
Correct |
588 ms |
186564 KB |
Output is correct |
| 29 |
Correct |
599 ms |
183204 KB |
Output is correct |
| 30 |
Correct |
553 ms |
194336 KB |
Output is correct |
| 31 |
Correct |
417 ms |
147920 KB |
Output is correct |
| 32 |
Correct |
405 ms |
189860 KB |
Output is correct |
