// boi2013 day2 p2
#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;
#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
using f80 = long double;
#pragma endregion
using grid_t = vector<string>;
const vi16 dx = {1, -1, 0, 0};
const vi16 dy = {0, 0, 1, -1};
bool inside(p32 a, int row, int col)
{
return a.first >= 0 && a.first < row &&
a.second >= 0 && a.second < col;
}
// sauce: https://judge.yosupo.jp/submission/76471
template <uint32_t N>
struct Bitset
{
using u64 = std::uint64_t;
using u32 = std::uint32_t;
using i32 = std::int32_t;
private:
static constexpr u64 ONE = 1;
static constexpr u64 ZERO = 0;
static constexpr u64 ALL_MASK = ~ZERO;
static constexpr u32 BITS = sizeof(u64) * CHAR_BIT;
static constexpr u32 ALL = BITS - 1;
static constexpr u32 CAPACITY = (N + BITS - 1) / BITS;
static constexpr u32 REMAINING = N & ALL;
static constexpr u64 CLEANUP_MASK = ~(ALL_MASK << REMAINING);
u64 a[CAPACITY];
/**
* storage:
* a[0] = bit_63, ..., bit_0
* a[1] = bit_127, ..., bit_64
* ...
*
* semantics of <<= and >>= : usual <<= and >>= semantics for u64
*/
// NOTE: range violations are undefined behaviour and are unchecked
struct reference
{
private:
u32 pos;
u64 *a;
public:
reference(u32 p, u64 *aa) : pos(p), a(aa) {}
reference &operator=(bool x) noexcept
{
if (x)
*a |= ONE << pos;
else
*a &= ~(ONE << pos);
return *this;
}
reference &operator=(const reference &x) noexcept
{
if ((*x.a >> x.pos) & 1)
*a |= ONE << pos;
else
*a &= ~(ONE << pos);
return *this;
}
operator bool() const noexcept { return (*a >> pos) & 1; }
bool operator~() const noexcept { return !((*a >> pos) & 1); }
reference &flip() noexcept { *a ^= ONE << pos; }
};
inline void cleanup() noexcept { a[CAPACITY - 1] &= CLEANUP_MASK; }
public:
constexpr Bitset() noexcept
{
static_assert(BITS == 64, "Won't work on this architecture");
static_assert(N > 0, "Size of parameter should be a positive integer");
reset();
};
constexpr Bitset(u64 x) noexcept : Bitset() { a[0] = x; };
constexpr Bitset(const std::string &x) : Bitset()
{
#ifdef DEBUG
if (x.size() > N * BITS)
throw std::out_of_range("String is too large to convert to Bitset");
#endif
u32 cur_loc = 0;
u32 bit = 0;
for (const auto c : x)
{
#ifdef DEBUG
if (c != '0' && c != '1')
throw std::invalid_argument(
"String should consist of only 0s and 1s");
#endif
a[cur_loc] |= u64(c - '0') << (bit++);
if (bit == BITS)
bit = 0, ++cur_loc;
}
}
constexpr Bitset(const Bitset &b)
{
std::copy(std::begin(b.a), std::end(b.a), std::begin(a));
}
bool operator==(const Bitset &b) const
{
return std::equal(std::begin(a), std::end(a), std::begin(b.a));
}
bool operator!=(const Bitset &b) const { return !(*this == b); }
constexpr bool operator[](u32 pos) const
{
#ifdef DEBUG
assert(("Bitset index out of range, UB", pos >= 0 && pos < N));
#endif
return (a[pos / BITS] >> (pos & ALL)) & 1;
}
reference operator[](u32 pos)
{
#ifdef DEBUG
assert(("Bitset index out of range, UB", pos >= 0 && pos < N));
#endif
return reference(pos & ALL, a + pos / BITS);
}
std::string to_string() const
{
std::string s(N, '0');
auto it = s.data() + N - 1;
for (u32 i = 0; i < N; ++i)
*(it--) += (a[i / BITS] >> (i & ALL)) & 1;
return s;
}
u32 count() const noexcept
{
u32 ans = 0;
for (u32 i = 0; i < CAPACITY; ++i)
ans += __builtin_popcountll(a[i]);
return ans;
}
u32 size() const noexcept { return N; }
#define IMPLEMENT(op) \
Bitset &operator op(const Bitset &b) noexcept \
{ \
for (u32 i = 0; i < CAPACITY; ++i) \
a[i] op b.a[i]; \
return *this; \
}
IMPLEMENT(&=)
IMPLEMENT(|=)
IMPLEMENT(^=)
#undef IMPLEMENT
Bitset &flip() noexcept
{
for (u32 i = 0; i < CAPACITY; ++i)
a[i] = ~a[i];
cleanup();
return *this;
}
Bitset operator~() const noexcept { return Bitset(*this).flip(); }
Bitset &operator<<=(u32 n) noexcept
{
if (n > N)
{
reset();
return *this;
}
if (__builtin_expect(n != 0, 1))
{
const u32 loc = n / BITS;
const u32 pos = n & ALL;
if (pos == 0)
for (u32 i = CAPACITY - 1; i != loc - 1; --i)
a[i] = a[i - loc];
else
{
const u32 complement = BITS - pos;
for (u32 i = CAPACITY - 1; i != loc - 1; --i)
a[i] = (a[i - loc] << pos) | (a[i - loc - 1] >> complement);
a[loc] = a[0] << pos;
}
std::fill(std::begin(a), std::begin(a) + loc, 0);
cleanup();
}
return *this;
}
// 01000 -> 00100
Bitset &operator>>=(u32 n) noexcept
{
if (n > N)
{
reset();
return *this;
}
if (__builtin_expect(n != 0, 1))
{
const u32 loc = n / BITS;
const u32 pos = n & ALL;
const u32 l = CAPACITY - 1 - loc;
if (pos == 0)
for (u32 i = 0; i <= l; ++i)
a[i] = a[i + loc];
else
{
const u32 complement = BITS - pos;
for (u32 i = 0; i < l; ++i)
a[i] = (a[i + loc] >> pos) | (a[i + loc + 1] << complement);
a[l] = a[CAPACITY - 1] >> pos;
}
std::fill(std::begin(a) + l + 1, std::end(a), 0);
cleanup();
}
return *this;
}
Bitset operator<<(u32 n) const noexcept { return Bitset(*this) <<= n; }
Bitset operator>>(u32 n) const noexcept { return Bitset(*this) >>= n; }
void reset() noexcept { std::fill(std::begin(a), std::end(a), 0); }
void set() noexcept
{
std::fill(std::begin(a), std::end(a), ALL_MASK);
cleanup();
}
// warning: these use ints and not u
i32 find_first_set() const noexcept
{
for (i32 i = 0; i < (i32)CAPACITY; ++i)
{
u64 w = a[i];
if (w)
return i * BITS + __builtin_ctzll(w);
}
return N;
}
i32 find_first_unset() const noexcept
{
for (i32 i = 0; i < CAPACITY; ++i)
{
u64 w = ~a[i];
if (w)
return i * BITS + __builtin_ctzll(w);
}
return N;
}
i32 find_next_set(i32 i) const noexcept
{
++i;
if (i >= BITS * CAPACITY)
return N;
i32 loc = i / BITS;
u64 w = a[loc] & (ALL_MASK << (i & ALL));
if (w)
return loc * BITS + __builtin_ctzll(w);
for (++loc; loc < CAPACITY; ++loc)
{
w = a[loc];
if (w)
return loc * BITS + __builtin_ctzll(w);
}
return N;
}
i32 find_next_unset(i32 i) const noexcept
{
++i;
if (i >= BITS * CAPACITY)
return N;
i32 loc = i / BITS;
u64 w = (~a[loc]) & (ALL_MASK << (i & ALL));
if (w)
return loc * BITS + __builtin_ctzll(w);
for (++loc; loc < CAPACITY; ++loc)
{
w = ~a[loc];
if (w)
return loc * BITS + __builtin_ctzll(w);
}
return N;
}
i32 find_prev_set(i32 i) const noexcept
{
--i;
if (i < 0)
return -1;
i32 loc = i / BITS;
u64 w = a[loc] & (ALL_MASK >> (ALL ^ (i & ALL)));
if (w)
return loc * BITS + (ALL ^ __builtin_clzll(w));
for (--loc; loc >= 0; --loc)
{
w = a[loc];
if (w)
return loc * BITS + (ALL ^ __builtin_clzll(w));
}
return -1;
}
i32 find_prev_unset(i32 i) const noexcept
{
--i;
if (i < 0)
return -1;
i32 loc = i / BITS;
u64 w = (~a[loc]) & (ALL_MASK >> (ALL ^ (i & ALL)));
if (w)
return loc * BITS + (ALL ^ __builtin_clzll(w));
for (--loc; loc >= 0; --loc)
{
w = ~a[loc];
if (w)
return loc * BITS + (ALL ^ __builtin_clzll(w));
}
return -1;
}
i32 find_next_set(i32 i, i32 max_iter) const noexcept
{
++i;
if (i >= BITS * CAPACITY)
return N;
i32 loc = i / BITS;
u64 w = a[loc] & (ALL_MASK << (i & ALL));
if (w)
return loc * BITS + __builtin_ctzll(w);
int iter = 0;
for (++loc; loc < CAPACITY && iter < max_iter; ++loc, ++iter)
{
w = a[loc];
if (w)
return loc * BITS + __builtin_ctzll(w);
}
return N;
}
i32 find_next_unset(i32 i, i32 max_iter) const noexcept
{
++i;
if (i >= BITS * CAPACITY)
return N;
i32 loc = i / BITS;
u64 w = (~a[loc]) & (ALL_MASK << (i & ALL));
if (w)
return loc * BITS + __builtin_ctzll(w);
int iter = 0;
for (++loc; loc < CAPACITY && iter < max_iter; ++loc, ++iter)
{
w = ~a[loc];
if (w)
return loc * BITS + __builtin_ctzll(w);
}
return N;
}
i32 find_prev_set(i32 i, i32 max_iter) const noexcept
{
--i;
if (i < 0)
return -1;
i32 loc = i / BITS;
u64 w = a[loc] & (ALL_MASK >> (ALL ^ (i & ALL)));
if (w)
return loc * BITS + (ALL ^ __builtin_clzll(w));
int iter = 0;
for (--loc; loc >= 0 && iter < max_iter; --loc, ++iter)
{
w = a[loc];
if (w)
return loc * BITS + (ALL ^ __builtin_clzll(w));
}
return -1;
}
i32 find_prev_unset(i32 i, i32 max_iter) const noexcept
{
--i;
if (i < 0)
return -1;
i32 loc = i / BITS;
u64 w = (~a[loc]) & (ALL_MASK >> (ALL ^ (i & ALL)));
if (w)
return loc * BITS + (ALL ^ __builtin_clzll(w));
int iter = 0;
for (--loc; loc >= 0 && iter < max_iter; --loc, ++iter)
{
w = ~a[loc];
if (w)
return loc * BITS + (ALL ^ __builtin_clzll(w));
}
return -1;
}
i32 find_last_set() const noexcept
{
for (i32 i = CAPACITY - 1; i >= 0; --i)
{
u64 w = a[i];
if (w)
return i * BITS + (ALL ^ __builtin_clzll(w));
}
return -1;
}
i32 find_last_unset() const noexcept
{
for (i32 i = CAPACITY - 1; i >= 0; --i)
{
u64 w = ~a[i];
if (w)
return i * BITS + (ALL ^ __builtin_clzll(w));
}
return -1;
}
// i32 find_kth_set(i32 k) const noexcept {}
// i32 find_kth_unset(i32 k) const noexcept {}
// i32 find_kth_next_set(i32 i, i32 k) const noexcept {}
// i32 find_kth_next_unset(i32 i, i32 k) const noexcept {}
// i32 find_kth_last_set(i32 k) const noexcept {}
// i32 find_kth_last_unset(i32 k) const noexcept {}
// return [l, r)
u64 slice(const u32 l, const u32 r) const
{
#ifdef DEBUG
assert(l <= N);
assert(r <= N);
#endif
if (l >= r)
return 0;
// 0 <= l < r <= N
u32 i1 = l / BITS;
u32 pos1 = l & ALL;
u32 i2 = (r - 1) / BITS;
u32 pos2 = (r - 1) & ALL;
if (i1 == i2)
{
return (a[i1] & (ALL_MASK >> (ALL - pos2))) >> pos1;
}
else
{
#ifdef DEBUG
assert(i2 == i1 + 1);
#endif
return (a[i1] >> pos1) |
((a[i2] & (ALL_MASK >> (ALL - pos2))) << (BITS - pos1));
}
}
std::string to_string_debug() const
{
std::string s(CAPACITY * BITS, '0');
for (i32 i = 0; i < CAPACITY * BITS; ++i)
s[CAPACITY * BITS - 1 - i] += (a[i / BITS] >> (i & ALL)) & 1;
return s;
}
friend inline Bitset operator&(const Bitset &x, const Bitset &y) noexcept
{
Bitset result = x;
result &= y;
return result;
}
friend inline Bitset operator|(const Bitset &x, const Bitset &y) noexcept
{
Bitset result = x;
result |= y;
return result;
}
friend inline Bitset operator^(const Bitset &x, const Bitset &y) noexcept
{
Bitset result = x;
result ^= y;
return result;
}
friend std::ostream &operator<<(std::ostream &os, const Bitset &b)
{
return os << b.to_string();
}
friend std::istream &operator>>(std::istream &os, Bitset &b)
{
std::string s = "";
os >> s;
b = Bitset(s);
return os;
}
};
int main()
{
#ifndef _AAAAAAAAA
ios_base::sync_with_stdio(false);
cin.tie(0);
#else
freopen("tracks.in", "r", stdin);
#ifndef __linux__
atexit([]()
{
freopen("con", "r", stdin);
system("pause"); });
#endif
#endif
int row, col;
cin >> row >> col;
grid_t grid(row);
for (auto &r : grid)
{
cin >> r;
}
vvi32 dist(row, vi32(col, INT_MAX));
dist[0][0] = 1;
Bitset<(int)8e6> now, later;
now[0] = true;
int count_now = 1, count_later = 0;
int ans = 1;
while (count_now)
{
int k = now.find_first_set();
now[k] = false;
count_now--;
int r = k / col, c = k % col;
for (int i = 0; i < (int)dx.size(); i++)
{
int n_r = r + dx[i];
int n_c = c + dy[i];
if (!inside({n_r, n_c}, row, col) ||
dist[n_r][n_c] != INT_MAX ||
grid[n_r][n_c] == '.')
{
continue;
}
if (grid[r][c] == grid[n_r][n_c])
{
dist[n_r][n_c] = dist[r][c];
ans = max(ans, dist[n_r][n_c]);
now[n_r * col + n_c] = true;
count_now++;
}
else
{
dist[n_r][n_c] = dist[r][c] + 1;
ans = max(ans, dist[n_r][n_c]);
later[n_r * col + n_c] = true;
count_later++;
}
}
if (!count_now)
{
swap(now, later);
swap(count_now, count_later);
}
}
cout << ans << '\n';
return 0;
}
