//Alt-Z on selected lines will collapse them
//Alt-Z on an indented block's top line will collapse that block
//Alt-Z on a folded block will expand it
//Alt-X will collapse all blocks on the deepest indention column (you can keep pressing Alt-X until all indention levels are folded)
//Shift-Alt-X will expand all the collapsed blocks
#include <bits/stdc++.h>
#include <cassert>
#define all(x) x.begin(), x.end()
#define debug(x) cerr << "[" << (#x) << " is " << (x) << "] "
#define debugl(x) cerr << "[" << (#x) << " is " << (x) << "]" << endl
#define eb emplace_back
#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define len(x) ((int) sizeof(x)/sizeof(x[0]))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define output_time cerr << "Time elapsed: " << 1000*clock() / CLOCKS_PER_SEC << "ms" << endl
#define pb push_back
#define sep cerr << "-----------------------------" << endl
#define test_cases int MMR; cin>>MMR; for (int i = 0; i < MMR; i++) solve()
#define test_input freopen("input.txt", "r", stdin)
#define test_local freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); freopen("error.txt", "w", stderr)
using ld = long double;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using namespace std;
using pii = pair<int, int>;
using pld = pair<ld, ld>;
using pll = pair<ll, ll>;
template<class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<class T> using maxpq = priority_queue<T, vector<T>>;
const int INTMAX = 2147483647;
const int INTMIN = -2147483647;
const ll LLMAX = 9223372036854775807;
const ll LLMIN = -9223372036854775807;
const ll MOD = 1000000007;
const ll MOD998 = 998224353;
const ld pi = 3.1415926535897932385;
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
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<typename K, typename V> using umap = unordered_map<K, V, custom_hash>;
template<typename K, typename V> using umultimap = unordered_multimap<K, V, custom_hash>;
template<typename T> using uset = unordered_set<T, custom_hash>;
template<typename T> using umultiset = unordered_multiset<T, custom_hash>;
void open(const string& s) {
string a = s + ".in";
string b = s + ".out";
freopen(a.c_str(), "r", stdin);
freopen(b.c_str(), "w", stdout);
}
template<typename A, typename B> ostream& operator<<(ostream &out, pair<A, B> const &pair);
template<typename T> ostream& operator<<(ostream &out, uset<T> const &s);
template<typename T> ostream& operator<<(ostream &out, set<T> const &s);
template<typename T> ostream& operator<<(ostream &out, multiset<T> const &s);
template<typename T> ostream& operator<<(ostream &out, umultiset<T> const &s);
template<typename K, typename V> ostream& operator<<(ostream &out, multimap<K, V> const &m);
template<typename K, typename V> ostream& operator<<(ostream &out, umultimap<K, V> const &m);
template<typename T> ostream& operator<<(ostream &out, vector<T> const &v);
template<typename K, typename V> ostream& operator<<(ostream &out, map<K, V> const &m);
template<typename K, typename V> ostream& operator<<(ostream &out, umap<K, V> const &m);
template<typename A, typename B> ostream& operator<<(ostream &out, pair<A, B> const &pair) {
out << "(" << pair.first << ", " << pair.second;
return out << ")";
}
template<typename T> ostream& operator<<(ostream &out, uset<T> const &s) {
out << "["; int c = 0;
for (T &i : s) {if (c) out << ", "; out << i; c++;}
return out << "]";
}
template<typename T> ostream& operator<<(ostream &out, set<T> const &s) {
out << "["; int c = 0;
for (T &i : s) {if (c) out << ", "; out << i; c++;}
return out << "]";
}
template<typename T> ostream& operator<<(ostream &out, vector<T> const &v) {
out << "[";
for (int i = 0; i < v.size(); i++) {if (i) out << ", "; out << v[i];}
return out << "]";
}
template<typename K, typename V> ostream& operator<<(ostream &out, map<K, V> const &m) {
out << "{"; int c = 0;
for (const auto &pair : m) {if (c) out << ", "; out << pair.first << "=" << pair.second; c++;}
return out << "}";
}
template<typename K, typename V> ostream& operator<<(ostream &out, umap<K, V> const &m) {
out << "{"; int c = 0;
for (const auto &pair : m) {if (c) out << ", "; out << pair.first << "=" << pair.second; c++;}
return out << "}";
}
template<typename T> ostream& operator<<(ostream &out, multiset<T> const &s) {
out << "["; int c = 0;
for (T &i : s) {if (c) out << ", "; out << i; c++;}
return out << "]";
}
template<typename T> ostream& operator<<(ostream &out, umultiset<T> const &s) {
out << "["; int c = 0;
for (T &i : s) {if (c) out << ", "; out << i; c++;}
return out << "]";
}
template<typename K, typename V> ostream& operator<<(ostream &out, multimap<K, V> const &m) {
out << "{"; int c = 0;
for (const auto &pair : m) {if (c) out << ", "; out << pair.first << "=" << pair.second; c++;}
return out << "}";
}
template<typename K, typename V> ostream& operator<<(ostream &out, umultimap<K, V> const &m) {
out << "{"; int c = 0;
for (const auto &pair : m) {if (c) out << ", "; out << pair.first << "=" << pair.second; c++;}
return out << "}";
}
template<typename T> void next_vec(vector<T> &vec, int l) {
vec = vector<T>(l);
for (int i = 0; i < l; i++) cin >> vec[i];
}
template<typename A, typename B> void next_vec(vector<pair<A, B>> &vec, int l) {
vec = vector<pair<A, B>>(l);
for (int i = 0; i < l; i++) {
A a; B b; cin >> a >> b;
vec[i].first = a; vec[i].second = b;
}
}
template<typename T> void next_graph(vector<vector<T>> &adj, int l) {
adj = vector<vector<int>>(l);
for (int i = 0; i < l; i++) {
int a, b; cin >> a >> b;
a--; b--;
adj[a].pb(b);
adj[b].pb(a);
}
}
string join(vector<string> &vec, string &t) {
int l = vec.size();
string s;
for (int i = 0; i < l; i++) {
s += vec[i];
if (i != l-1) s += t;
}
return s;
}
ll combo(ll n, ll d) {
if (d > n) return 0;
if (d*2 > n) d = n-d;
if (d == 0) return 1;
ll res = n;
for (ll i = 2; i <= d; i++) {
res *= (n-i+1);
res /= i;
}
return res;
}
template<typename T> void shuffle_vec(vector<T> &vec) {
shuffle(vec.begin(), vec.end(), mt19937(random_device()()));
}
ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a%b);}
ll lcm(ll a, ll b) {return a/gcd(a, b)*b;}
vector<string> split(const string& str, const string& delim = " ") {
vector<string> tokens;
size_t prev = 0, pos = 0;
do {
pos = str.find(delim, prev);
if (pos == string::npos) pos = str.length();
string token = str.substr(prev, pos-prev);
if (!token.empty()) tokens.push_back(token);
prev = pos + delim.length();
}
while (pos < str.length() && prev < str.length());
return tokens;
}
template<typename T> int binary_search(vector<T> &vec, T &n) {
int l = vec.size();
int left = 0;
int right = l-1;
while (left != right) {
int mid = (left+right+1)/2;
if (vec[mid] > n) right = mid-1;
else left = mid;
}
return vec[left] == n ? left : -1;
}
template<typename T> vector<ll> prefix(vector<T> &vec) {
int l = vec.size(); assert(l);
vector<ll> pre(l); pre[0] = vec[0];
for (int i = 1; i < l; i++) pre[i] = pre[i-1]+vec[i];
return pre;
}
template<typename T> vector<ll> suffix(vector<T> &vec) {
int l = vec.size();
assert(l);
vector<ll> suf(l);
suf[l-1] = vec[l-1];
for (int i = l - 2; i >= 0; i--) suf[i] = suf[i+1] + vec[i];
return suf;
}
ll bs_lowest(const function<bool(ll)> &f, ll lo, ll hi) {
while (lo < hi) {
ll mid = (lo+hi)/2;
f(mid) ? hi = mid : lo = mid+1;
}
return lo;
}
ll bs_highest(const function<bool(ll)> &f, ll lo, ll hi) {
ll a = lo;
for (ll i = hi; i >= a; i /= 2) {
while (f(lo + i)) lo += i;
}
return lo;
}
template<typename T> T min(vector<T> &vec) {
assert(!vec.empty());
T a = vec[0];
for (T &i : vec) a = min(a, i);
return a;
}
template<typename T> T max(vector<T> &vec) {
assert(!vec.empty());
T a = vec[0];
for (T &i : vec) a = max(a, i);
return a;
}
template<typename T> ll sum(vector<T> &vec) {
ll sum = 0;
for (T &i : vec) sum += i;
return sum;
}
vector<bool> sieve(int n) {
vector<bool> vec(n+1, true);
vec[0] = false;
vec[1] = false;
for (int i = 2; i <= n; i++) {
if (vec[i]) {
for (int j = i; j <= n; j += i) vec[i] = false;
}
}
return vec;
}
bool prime(ll n) {
for (ll i = 2; i*i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
template <int MOD_> struct modnum {
template<typename T>
modnum(T value) {
v = value % MOD_;
if (v < 0) v += MOD_;
}
static constexpr int MOD = MOD_;
static_assert(MOD_ > 0, "MOD must be positive");
int v;
private:
using ll = long long;
static int minv(int a, int m) {
a %= m;
assert(a);
return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
}
public:
modnum() : v(0) {}
explicit modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
explicit operator int() const { return v; }
explicit operator long long() const { return v; }
explicit operator unsigned int() const { return v; }
explicit operator unsigned long long() const { return v; }
friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }
friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
friend bool operator <= (const modnum& a, const modnum& b) { return a.v <= b.v; }
friend bool operator >= (const modnum& a, const modnum& b) { return a.v >= b.v; }
friend bool operator > (const modnum& a, const modnum& b) { return a.v > b.v; }
friend bool operator < (const modnum& a, const modnum& b) { return a.v < b.v; }
template<typename T>
friend bool operator == (const modnum& a, const T& b) {return a.v == b;}
template<typename T>
friend bool operator != (const modnum& a, const T& b) {return a.v != b;}
template<typename T>
friend bool operator >= (const modnum& a, const T& b) {return a.v >= b;}
template<typename T>
friend bool operator <= (const modnum& a, const T& b) {return a.v <= b;}
template<typename T>
friend bool operator > (const modnum& a, const T& b) {return a.v > b;}
template<typename T>
friend bool operator < (const modnum& a, const T& b) {return a.v < b;}
modnum inv() const {
modnum res;
res.v = minv(v, MOD);
return res;
}
friend modnum inv(const modnum& m) { return m.inv(); }
modnum neg() const {
modnum res;
res.v = v ? MOD-v : 0;
return res;
}
friend modnum neg(const modnum& m) { return m.neg(); }
modnum operator- () const {
return neg();
}
modnum operator+ () const {
return modnum(*this);
}
modnum& operator ++ () {
v ++;
if (v == MOD) v = 0;
return *this;
}
modnum& operator -- () {
if (v == 0) v = MOD;
v --;
return *this;
}
modnum& operator += (const modnum& o) {
v -= MOD-o.v;
v = (v < 0) ? v + MOD : v;
return *this;
}
modnum& operator -= (const modnum& o) {
v -= o.v;
v = (v < 0) ? v + MOD : v;
return *this;
}
modnum& operator *= (const modnum& o) {
v = int(ll(v) * ll(o.v) % MOD);
return *this;
}
modnum& operator /= (const modnum& o) {
return *this *= o.inv();
}
friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};
template <typename T> T power(T a, ll b) {
assert(b >= 0);
T r = 1; while (b) { if (b & 1) r *= a; b >>= 1; a *= a; } return r;
}
using mod = modnum<(int) 1e9+7>;
#define inf 1e9
int h, w;
vector<string> vec;
int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};
vector<vector<int>> dis;
vector<vector<bool>> seen;
bool valid(int i, int j) {return i >= 0 && i < h && j >= 0 && j < w && vec[i][j] != '.';}
int bfs() {
int mex = 0;
deque<pii> d;
d.pb(mp(0, 0));
while (!d.empty()) {
pii cur = d.front();
d.pop_front();
int i = cur.first, j = cur.second;
mex = max(mex, dis[i][j]);
for (int k = 0; k < 4; k++) {
int a = i+dy[k], b = j+dx[k];
if (valid(a, b) && !dis[a][b]) {
if (vec[a][b] != vec[i][j]) {
dis[a][b] = dis[i][j]+1;
d.pb(mp(a, b));
}
else {
dis[a][b] = dis[i][j];
d.push_front(mp(a, b));
}
}
}
}
return mex;
}
void solve() {
cin >> h >> w;
vec = vector<string>(h);
dis = vector<vector<int>>(h, vector<int>(w));
seen = vector<vector<bool>>(h, vector<bool>(w));
dis[0][0] = 1;
for (int i = 0; i < h; i++) cin >> vec[i];
cout << bfs() << endl;
}
int main() {
FAST_IO;
//test_input;
//test_local;
//open("nocross");
solve();
output_time;
}
Compilation message
tracks.cpp: In function 'void open(const string&)':
tracks.cpp:64:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
64 | freopen(a.c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:65:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
65 | freopen(b.c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
1644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
7 ms |
1388 KB |
Output is correct |
| 5 |
Correct |
2 ms |
748 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
2 ms |
748 KB |
Output is correct |
| 11 |
Correct |
2 ms |
620 KB |
Output is correct |
| 12 |
Correct |
5 ms |
876 KB |
Output is correct |
| 13 |
Correct |
2 ms |
748 KB |
Output is correct |
| 14 |
Correct |
2 ms |
748 KB |
Output is correct |
| 15 |
Correct |
12 ms |
1644 KB |
Output is correct |
| 16 |
Correct |
13 ms |
1644 KB |
Output is correct |
| 17 |
Correct |
8 ms |
1672 KB |
Output is correct |
| 18 |
Correct |
7 ms |
1388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
43 ms |
8428 KB |
Output is correct |
| 3 |
Correct |
223 ms |
83052 KB |
Output is correct |
| 4 |
Correct |
68 ms |
19692 KB |
Output is correct |
| 5 |
Correct |
185 ms |
46828 KB |
Output is correct |
| 6 |
Correct |
799 ms |
96360 KB |
Output is correct |
| 7 |
Correct |
3 ms |
1132 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1004 KB |
Output is correct |
| 9 |
Correct |
2 ms |
620 KB |
Output is correct |
| 10 |
Correct |
1 ms |
492 KB |
Output is correct |
| 11 |
Correct |
2 ms |
1132 KB |
Output is correct |
| 12 |
Correct |
1 ms |
492 KB |
Output is correct |
| 13 |
Correct |
42 ms |
8428 KB |
Output is correct |
| 14 |
Correct |
24 ms |
5100 KB |
Output is correct |
| 15 |
Correct |
18 ms |
5484 KB |
Output is correct |
| 16 |
Correct |
20 ms |
3692 KB |
Output is correct |
| 17 |
Correct |
116 ms |
21320 KB |
Output is correct |
| 18 |
Correct |
89 ms |
20972 KB |
Output is correct |
| 19 |
Correct |
72 ms |
19820 KB |
Output is correct |
| 20 |
Correct |
58 ms |
18132 KB |
Output is correct |
| 21 |
Correct |
138 ms |
48364 KB |
Output is correct |
| 22 |
Correct |
181 ms |
46700 KB |
Output is correct |
| 23 |
Correct |
234 ms |
40428 KB |
Output is correct |
| 24 |
Correct |
137 ms |
47212 KB |
Output is correct |
| 25 |
Correct |
475 ms |
83180 KB |
Output is correct |
| 26 |
Correct |
955 ms |
113788 KB |
Output is correct |
| 27 |
Correct |
793 ms |
101524 KB |
Output is correct |
| 28 |
Correct |
803 ms |
96488 KB |
Output is correct |
| 29 |
Correct |
799 ms |
94184 KB |
Output is correct |
| 30 |
Correct |
814 ms |
98664 KB |
Output is correct |
| 31 |
Correct |
649 ms |
53704 KB |
Output is correct |
| 32 |
Correct |
822 ms |
99980 KB |
Output is correct |
