# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|
637257 | | iee | Zoo (COCI19_zoo) | C++17 | | 118 ms | 6412 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// iee
#include <bits/stdc++.h>
#define rep(i, a, b) for (auto i = (a); i <= (b); ++i)
#define per(i, a, b) for (auto i = (a); i >= (b); --i)
#define fi first
#define se second
using ll = long long;
using ull = unsigned long long;
using namespace std;
void work(int);
template <class T> void read(T &x) {
x = 0; int f = 1, ch = getchar();
while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
while (isdigit(ch)) x = x * 10 + (ch - '0'), ch = getchar();
x *= f;
}
int main() {
int TT = 1; // cin >> TT;
rep(CAS, 1, TT)
work(CAS);
return 0;
}
const int N = 1005;
int n, m;
char s[N][N];
int dis[N][N];
const int nxt[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
void work(int CASE) {
scanf("%d%d", &n, &m);
rep(i, 1, n) scanf("%s", s[i] + 1);
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> q;
memset(dis, 0x3f, sizeof dis);
q.emplace(dis[1][1] = 1, 1, 1);
rep(i, 1, n) rep(j, 1, m) if (s[i][j] == '*') dis[i][j] = 0;
while (!q.empty()) {
int d, ux, uy;
tie(d, ux, uy) = q.top();
q.pop();
if (dis[ux][uy] != d) continue;
// cerr << d << ' ' << ux << ' ' << uy << '\n';
rep(dir, 0, 3) {
int vx = ux + nxt[dir][0];
int vy = uy + nxt[dir][1];
if (vx < 1 || vx > n || vy < 1 || vy > m) continue;
int cost = d + (s[ux][uy] != s[vx][vy]);
if (dis[vx][vy] > cost) {
dis[vx][vy] = cost;
q.emplace(cost, vx, vy);
}
}
}
int mx = 0;
rep(i, 1, n) rep(j, 1, m)
mx = max(mx, dis[i][j]);
cout << mx;
}
Compilation message (stderr)
zoo.cpp: In function 'void work(int)':
zoo.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
32 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
zoo.cpp:33:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | rep(i, 1, n) scanf("%s", s[i] + 1);
| ~~~~~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |