oj.uz

답안 #5872

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
5872 2014-05-20T11:44:04 Z gs12037 토마토 (KOI13_tomato) C++
16 / 16
 416 ms 10320 KB 
#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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 9164 KB Output is correct
2 Correct 0 ms 9164 KB Output is correct
3 Correct 0 ms 9164 KB Output is correct
4 Correct 0 ms 9164 KB Output is correct

Subtask #2
1.6 / 1.6

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 9164 KB Output is correct
2 Correct 0 ms 9164 KB Output is correct
3 Correct 0 ms 9164 KB Output is correct
4 Correct 0 ms 9164 KB Output is correct

Subtask #3
1.6 / 1.6

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 9164 KB Output is correct
2 Correct 0 ms 9164 KB Output is correct
3 Correct 0 ms 9164 KB Output is correct
4 Correct 0 ms 9164 KB Output is correct

Subtask #4
1.6 / 1.6

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 9548 KB Output is correct
2 Correct 12 ms 9744 KB Output is correct
3 Correct 0 ms 9164 KB Output is correct
4 Correct 0 ms 9164 KB Output is correct

Subtask #5
1.6 / 1.6

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 9164 KB Output is correct
2 Correct 0 ms 9164 KB Output is correct
3 Correct 12 ms 9164 KB Output is correct
4 Correct 4 ms 9164 KB Output is correct

Subtask #6
1.6 / 1.6

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 9164 KB Output is correct
2 Correct 4 ms 9164 KB Output is correct
3 Correct 0 ms 9164 KB Output is correct
4 Correct 4 ms 9164 KB Output is correct

Subtask #7
1.6 / 1.6

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 9356 KB Output is correct
2 Correct 28 ms 9164 KB Output is correct
3 Correct 36 ms 9356 KB Output is correct
4 Correct 24 ms 9164 KB Output is correct

Subtask #8
1.6 / 1.6

# 결과 실행 시간 메모리 Grader output
1 Correct 160 ms 9548 KB Output is correct
2 Correct 136 ms 9744 KB Output is correct
3 Correct 16 ms 9356 KB Output is correct
4 Correct 24 ms 9164 KB Output is correct

Subtask #9
1.6 / 1.6

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 9356 KB Output is correct
2 Correct 116 ms 9164 KB Output is correct
3 Correct 32 ms 9356 KB Output is correct
4 Correct 76 ms 9164 KB Output is correct

Subtask #10
1.6 / 1.6

# 결과 실행 시간 메모리 Grader output
1 Correct 380 ms 9744 KB Output is correct
2 Correct 416 ms 10320 KB Output is correct
3 Correct 132 ms 9164 KB Output is correct
4 Correct 112 ms 9164 KB Output is correct