Submission #754631

#	Time	Username	Problem	Language	Result	Execution time	Memory
754631		MilosMilutinovic	Zoo (COCI19_zoo)	C++14	110 / 110	47 ms	6228 KiB

zoo

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int inf = 0x3f3f3f3f;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
int n, m, dist[N][N];
char s[N][N];
bool valid(int x, int y) {
    return 1 <= x && x <= n && 1 <= y && y <= m && s[x][y] != '*';
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s[i] + 1);
    }
    deque<pair<int, int>> dq;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dist[i][j] = inf;
        }
    }
    dist[1][1] = 1;
    dq.emplace_back(1, 1);
    while (!dq.empty()) {
        pair<int, int> p = dq.front();
        dq.pop_front();
        int x = p.first;
        int y = p.second;
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (!valid(nx, ny)) {
                continue;
            }
            int w = (s[x][y] != s[nx][ny] ? 1 : 0);
            if (dist[nx][ny] > dist[x][y] + w) {
                dist[nx][ny] = dist[x][y] + w;
                if (w == 0) {
                    dq.emplace_front(nx, ny);
                } else {
                    dq.emplace_back(nx, ny);
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (valid(i, j)) {
                ans = max(ans, dist[i][j]);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

zoo.cpp: In function 'int main()':
zoo.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
zoo.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf("%s", s[i] + 1);
      |         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 45 / 45
• Subtask 2: 65 / 65