#include <bits/stdc++.h>
#define mod 1000000007
#define init(arr, val) memset(arr, val, sizeof(arr))
#define fr(a,b) for(ll i = a; i < b; i++)
#define loop(i, a, b) for (ll i = a; i < b; i++)
#define loopr(i, a, b) for (ll i = a; i >= b; i--)
#define loops(i, a, b, step) for (ll i = a; i < b; i += step)
#define looprs(i, a, b, step) for (ll i = a; i >= b; i -= step)
#define ull unsigned long long int
#define ll long long int
#define P pair
#define pll pair<long long, long long>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define PUU pair<unsigned long long int, unsigned long long int>
#define L list
#define V vector
#define D deque
#define ST set
#define MS multiset
#define M map
#define UM unordered_map
#define mp make_pair
#define pb push_back
#define pf push_front
#define MM multimap
#define F first
#define S second
#define IT iterator
#define RIT reverse_iterator
#define fast_io \
ios_base::sync_with_stdio(false); \
cin.tie(); \
cout.tie()
#define FILE_READ_IN freopen("input.txt", "r", stdin);
#define FILE_READ_OUT freopen("output.txt", "w", stdout);
#define prDouble(x) cout << fixed << setprecision(10) << x
#define all(a) a.begin(), a.end()
#define ld long double
#define inf (1LL<<60)
using namespace std;
const ll maxn = 2e5 + 1;
const double pi = acos(-1);
vector<pii> dir = { {1,0}, {0,1}, {0, -1}, {-1, 0} };
int main() {
fast_io;
int tests = 1;
// cin >> tests;
for (int test_case = 1; test_case <= tests; test_case++) {
int h, w; cin >> h >> w;
char a[h][w];
fr(0, h) {
loop(j, 0, w) cin >> a[i][j];
}
vector<int> d(h * w, 1e9);
d[(h - 1) * w] = 0;
if (a[h - 1][0] != '.') d[(h - 1) * w] = 1;
deque<pair<int, int>> q;
q.push_back(make_pair(h - 1, 0));
int res = 0;
while (!q.empty()) {
auto cur = q.front();
int curf = cur.first;
int curs = cur.second;
q.pop_front();
auto dis = d[curf * w + curs];
for (auto i : dir) {
// pii j = cur + i;
int jf = curf + i.first;
int js = curs + i.second;
if (jf < 0) continue;
if (jf >= h) continue;
if (js < 0) continue;
if (js >= w) continue;
int e = 0;
// if (a[curf][curs] != '.') {
e = (a[curf][curs] != a[jf][js]);
// }
if (dis + e < d[jf * w + js]) {
d[jf * w + js] = dis + e;
if (e == 0) q.push_front({ jf,js });
else q.push_back({ jf,js });
}
}
}
fr(0, h * w) {
if (a[i / w][i % w] != '.') res = max(res, d[i]);
}
cout << res << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
1628 KB |
Output isn't correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Incorrect |
6 ms |
1232 KB |
Output isn't correct |
| 5 |
Incorrect |
5 ms |
900 KB |
Output isn't correct |
| 6 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 8 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 10 |
Incorrect |
3 ms |
860 KB |
Output isn't correct |
| 11 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 12 |
Incorrect |
4 ms |
860 KB |
Output isn't correct |
| 13 |
Incorrect |
4 ms |
860 KB |
Output isn't correct |
| 14 |
Incorrect |
4 ms |
860 KB |
Output isn't correct |
| 15 |
Incorrect |
11 ms |
1880 KB |
Output isn't correct |
| 16 |
Incorrect |
11 ms |
1624 KB |
Output isn't correct |
| 17 |
Incorrect |
11 ms |
1628 KB |
Output isn't correct |
| 18 |
Incorrect |
6 ms |
1372 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1036 KB |
Output isn't correct |
| 2 |
Incorrect |
58 ms |
11032 KB |
Output isn't correct |
| 3 |
Incorrect |
579 ms |
131336 KB |
Output isn't correct |
| 4 |
Incorrect |
151 ms |
19428 KB |
Output isn't correct |
| 5 |
Incorrect |
316 ms |
81568 KB |
Output isn't correct |
| 6 |
Incorrect |
667 ms |
90988 KB |
Output isn't correct |
| 7 |
Incorrect |
3 ms |
604 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 9 |
Incorrect |
3 ms |
860 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 11 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 12 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 13 |
Incorrect |
58 ms |
11192 KB |
Output isn't correct |
| 14 |
Incorrect |
33 ms |
6496 KB |
Output isn't correct |
| 15 |
Incorrect |
36 ms |
7504 KB |
Output isn't correct |
| 16 |
Incorrect |
25 ms |
4700 KB |
Output isn't correct |
| 17 |
Incorrect |
150 ms |
28868 KB |
Output isn't correct |
| 18 |
Incorrect |
169 ms |
29152 KB |
Output isn't correct |
| 19 |
Incorrect |
145 ms |
19280 KB |
Output isn't correct |
| 20 |
Incorrect |
121 ms |
27684 KB |
Output isn't correct |
| 21 |
Incorrect |
323 ms |
64388 KB |
Output isn't correct |
| 22 |
Incorrect |
330 ms |
81760 KB |
Output isn't correct |
| 23 |
Incorrect |
318 ms |
53532 KB |
Output isn't correct |
| 24 |
Incorrect |
320 ms |
69964 KB |
Output isn't correct |
| 25 |
Incorrect |
943 ms |
116708 KB |
Output isn't correct |
| 26 |
Correct |
412 ms |
110436 KB |
Output is correct |
| 27 |
Correct |
584 ms |
121996 KB |
Output is correct |
| 28 |
Incorrect |
671 ms |
90804 KB |
Output isn't correct |
| 29 |
Incorrect |
657 ms |
89812 KB |
Output isn't correct |
| 30 |
Incorrect |
629 ms |
96564 KB |
Output isn't correct |
| 31 |
Incorrect |
467 ms |
51028 KB |
Output isn't correct |
| 32 |
Incorrect |
591 ms |
101532 KB |
Output isn't correct |
