Submission #401319

#	Time	Username	Problem	Language	Result	Execution time	Memory
401319		hgmhc	토마토 (KOI13_tomato)	C++17	16 / 16	126 ms	11456 KiB

tomato

#include <iostream>
#include <queue>
#include <utility>
using namespace std;
using pi = pair<int,int>;
#define F first
#define S second
#define isInBoard(r,c) (r >= 0 && r < n && c >= 0 && c < m)
   
const int maxn = 1000, maxm = 1000;
int n, m, ans, tm[maxn][maxm], days[maxn][maxm];
bool visited[maxn][maxm], isThereNotRiped;
queue<pi> q;
 
void bfs(pi s, pi e) {
    if (isInBoard(e.F, e.S) && !visited[e.F][e.S] && !tm[e.F][e.S]) {
        visited[e.F][e.S] = true;
        days[e.F][e.S] = days[s.F][s.S]+1;
        q.push({e.F, e.S});
        ans = max(ans, days[e.F][e.S]);
    }
    return;
}
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> m >> n;
    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < m; ++c) {
            cin >> tm[r][c];
            if (!tm[r][c]) isThereNotRiped = true;
            else if (tm[r][c] == 1) {
                q.push({r, c});
                days[r][c] = 0; visited[r][c] = true;
            }
        }
    }
    if (!isThereNotRiped) {
        cout << 0;
        return 0;
    }
    while (!q.empty()) {
        pi s = q.front(); q.pop();
        tm[s.F][s.S] = 1;
        bfs(s, {s.F, s.S+1});
        bfs(s, {s.F+1, s.S});
        bfs(s, {s.F, s.S-1});
        bfs(s, {s.F-1, s.S});
    }
    for (int r = 0; r < n; ++r) for (int c = 0; c < m; ++c) {
        if (!tm[r][c]) {
            cout << -1;
            return 0;
        }
    }
    cout << ans;
    return 0;
}

• Subtask 1: 1.6 / 1.6
• Subtask 2: 1.6 / 1.6
• Subtask 3: 1.6 / 1.6
• Subtask 4: 1.6 / 1.6
• Subtask 5: 1.6 / 1.6
• Subtask 6: 1.6 / 1.6
• Subtask 7: 1.6 / 1.6
• Subtask 8: 1.6 / 1.6
• Subtask 9: 1.6 / 1.6
• Subtask 10: 1.6 / 1.6