[acmicpc] 7576. 토마토(BFS)

bfs로 구현해보았습니다

메모리초과, 시간초과, ... 틀렸습니다에 이은 결과 값!

---

#include <iostream>
#include <queue>
int x, y;
int arr[1000][1000];
int visit[1000][1000];
int depth[1000][1000];
using namespace std;
int d_x[4] = { 0, 0, 1, -1 }; 
int d_y[4] = { 1, -1, 0, 0 };
queue<int> qx;
queue<int> qy;
int min_value;
int cnt = 0;
int flag = 0;
void bfs() {
	while (!qx.empty() && !qy.empty()) {
		int temp_x = qx.front(); qx.pop();
		int temp_y = qy.front(); qy.pop();
		for (int k = 0; k < 4; k++) {
			int xx = temp_x + d_x[k];
			int yy = temp_y + d_y[k];
			if (xx >= 0 && xx < x && yy >=0 && yy < y) {
				if (arr[yy][xx] == 0 && visit[yy][xx] == -1) {
					flag = 1;
					qx.push(xx);
					qy.push(yy);
					visit[yy][xx] = visit[temp_y][temp_x] + 1;
					if (min_value < visit[yy][xx]) min_value = visit[yy][xx];
					cnt++;
				}
			}
		}
	}
}
int main(void) {
	cin >> x >> y;
	int minus = 0;
	for (int i = 0; i < y; i++) {
		for (int j = 0; j < x; j++) {
			cin >> arr[i][j];
			visit[i][j] = -1;
			if (arr[i][j] == -1) {
				minus++;
				visit[i][j] = 0;
			}
		}
	}
	for (int i = 0; i < y; i++) {
		for (int j = 0; j < x; j++) {
			if (arr[i][j]==1) {
				qx.push(j);
				qy.push(i);
				cnt++;
			}
		}
	}
	bfs();
	int min = min_value+flag; //flag는 영향을 받은 토마토의 유무를 체크(flag=1,하나라도 영향받음.)
	if (cnt < x*y-minus) min = -1; //방문안한 토마토가 있다면
	
	
	cout << min;
	return 0;
}

 

 

---

www.acmicpc.net/problem/7576