Submission #5872

#	Time	Username	Problem	Language	Result	Execution time	Memory
5872		gs12037	토마토 (KOI13_tomato)	C++98	16 / 16	416 ms	10320 KiB

tomato

#include <stdio.h>
#include <queue>
#define M 1009
using namespace std;
struct pp{
	int a, b, cost;
	pp(){}
	pp(int A, int B, int c){
		a = A; b = B; cost = c;
	}
	bool operator<(const pp &q)const{
		return cost > q.cost;
	}
};
priority_queue<pp> q;
int n, m, s[M][M], ans=-1, chk[M][M];
int x[4] = { 1, -1, 0, 0 }, y[4] = { 0, 0, 1, -1 };
int main(){
	int i, j;
	int A = 0, B = 0;
	scanf("%d %d", &n, &m);
	for (i = 1; i <= m; i++){
		for (j = 1; j <= n; j++){
			scanf("%d", &s[i][j]);
			if (s[i][j]==1) q.push(pp(i, j, 0));
			if (s[i][j] >= 0) A++;
		}
	}

	pp e;
	while (!q.empty()){
		e = q.top(); q.pop();
		if (chk[e.a][e.b]) continue;
		B++;
		chk[e.a][e.b] = 1;
		ans = max(ans, e.cost);
		for (i = 0; i<4; i++)
		if (1 <= e.a + x[i] && e.a + x[i] <= m && 1 <= e.b + y[i] && e.b + y[i] <= n && chk[e.a + x[i]][e.b + y[i]] == 0 && s[e.a+x[i]][e.b+y[i]] == 0) q.push(pp(e.a + x[i], e.b + y[i], e.cost + 1));
	}
	if (A == B) printf("%d", ans);
	else printf("-1");
	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