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 <stdio.h>
#define N 1000
#define M 1000
int max(int a, int b) { return a > b ? a : b; }
int di[] = { -1, 1, 0, 0 };
int dj[] = { 0, 0, -1, 1 };
int main() {
static char cc[N][M + 1];
static int dd[N][M], qu[N * M * 2];
int n, m, i, j, d, head, cnt;
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++)
scanf("%s", cc[i]);
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
dd[i][j] = n * m;
head = n * m, cnt = 0;
dd[0][0] = 0, qu[head + cnt++] = 0 * m + 0;
while (cnt) {
int ij = qu[cnt--, head++], h;
i = ij / m, j = ij % m, d = dd[i][j];
for (h = 0; h < 4; h++) {
int i_ = i + di[h], j_ = j + dj[h];
if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m && cc[i_][j_] != '*') {
if (cc[i_][j_] == cc[i][j]) {
if (dd[i_][j_] > d)
dd[i_][j_] = d, qu[cnt++, --head] = i_ * m + j_;
} else {
if (dd[i_][j_] > d + 1)
dd[i_][j_] = d + 1, qu[head + cnt++] = i_ * m + j_;
}
}
}
}
d = 0;
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
if (cc[i][j] != '*')
d = max(d, dd[i][j]);
printf("%d\n", d + 1);
return 0;
}
Compilation message (stderr)
zoo.c: In function 'main':
zoo.c:16:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | scanf("%d%d", &n, &m);
| ^~~~~~~~~~~~~~~~~~~~~
zoo.c:18:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | scanf("%s", cc[i]);
| ^~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |