This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define forw(i,a,b) for (int i = (a); i <= (b); i++)
#define ford(i,a,b) for (int i = (a); i >= (b); i--)
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define ff first
#define ss second
#define ALL(v) (v).begin(), (v).end()
#define nl '\n'
using namespace std;
template<class X, class Y>
bool minimize(X &x, const Y &y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template<class X, class Y>
bool maximize(X &x, const Y &y) {
if (x < y) {
x = y;
return true;
}
return false;
}
/* AHIHI */
#define MAX 4010
typedef long long ll;
typedef pair<int, int> pii;
const int dx[] = {-1,1,0,0}, dy[] = {0,0,-1,1};
int n,m,res,d[MAX][MAX];
char a[MAX][MAX];
bool ins(int u,int v)
{
return min(u,v) >= 1 && u <= n && v <= m;
}
void bfs()
{
deque<pii> q;
q.push_back({1,1});
d[1][1] = 1;
while (q.size()) {
pii c = q.front(); q.pop_front();
maximize(res, d[c.ff][c.ss]);
rep(i,0,4) {
int u = c.ff + dx[i], v = c.ss + dy[i];
if (ins(u,v) && d[u][v] == 0 && a[u][v]!='.') {
if (a[u][v] == a[c.ff][c.ss]) {
d[u][v] = d[c.ff][c.ss];
q.push_front({u,v});
}
else {
d[u][v] = d[c.ff][c.ss] + 1;
q.push_back({u,v});
}
}
}
}
}
void solve(int tc)
{
cin >> n >> m;
forw(i,1,n) forw(j,1,m) cin >> a[i][j];
bfs();
cout << res << nl;
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(0);
// string name = "HT";
// freopen((name + ".inp").c_str(),"r",stdin);
// freopen((name + ".out").c_str(),"w",stdout);
int T = 1;
// cin >> T;
forw(i,1,T) solve(i);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |