백준 7576번 C++

#include <iostream>

#include <queue>

using namespace std;

const int MAX = 1001;

int n, m;

int tomato[MAX][MAX];

int notomato = 0;

queue<pair<int, int>> finish;

typedef struct {

int a, b;

}Move;

Move mv[4] = { {1,0},{-1,0},{0,-1},{0,1} };

bool allfinish() {

int finishtomato = 0;

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

if(tomato[i][j] == 1)

finishtomato++;

}

}

return ((m*n - notomato) == finishtomato);

}

int bfs() {

int day = 0;

if (finish.size() == 0)

return -1;

while (!finish.empty()) {

int sizes = finish.size();

for (int i = 0; i < sizes; i++) {

int x = finish.front().first;

int y = finish.front().second;

finish.pop();

for (int k = 0; k < 4; k++) {

int mx = x + mv[k].a;

int my = y + mv[k].b;

if (mx >= 0 && mx < m && my >= 0 && my < n) {

if (tomato[mx][my] == 0) {

tomato[mx][my] = 1;

finish.push(make_pair(mx, my));

}

}

}

}

day++;

}

if (allfinish())

return day - 1;

else

return -1;

}

int mainc(void) {

cin >> m >> n;

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

cin >> tomato[i][j];

if (tomato[i][j] == 1)

finish.push(make_pair(i, j));

else if (tomato[i][j] == -1)

notomato++;

}

}

if ((m*n - notomato) == finish.size())

cout << 0 << endl;

else

cout << bfs() << endl;

return 0;

}