#include #include #include #include #include #include using namespace std; int Num, K; array dx = {1,0,-1,0}; array dy = {0,1,0,-1}; void SearchConnection(vector>& Map, vector>& visited, const array& pos) { queue> Path; Path.push(pos); visited[pos[0]][pos[1]] = true; while(!Path.empty()) { int count = 0; array cur = Path.front(); Path.pop(); // visited[cur[0]][cur[1]] = true; array E = {cur[0]+dy[0], cur[1]+dx[0]}; array N = {cur[0]+dy[1], cur[1]+dx[1]}; array W = {cur[0]+dy[2], cur[1]+dx[2]}; array S = {cur[0]+dy[3], cur[1]+dx[3]}; if(E[1] < K && !visited[E[0]][E[1]]) { if(Map[E[0]][E[1]] != 0) { Path.push(E); visited[E[0]][E[1]] = true; } else count++; } if(N[0] < Num && !visited[N[0]][N[1]]) { if(Map[N[0]][N[1]] != 0) { Path.push(N); visited[N[0]][N[1]] = true; } else count++; } if(W[1] >= 0 && !visited[W[0]][W[1]]) { if(Map[W[0]][W[1]] != 0) { Path.push(W); visited[W[0]][W[1]] = true; } else count++; } if(S[0] >=0 && !visited[S[0]][S[1]]) { if(Map[S[0]][S[1]] != 0) { Path.push(S); visited[S[0]][S[1]] = true; } else count++; } Map[cur[0]][cur[1]] = (Map[cur[0]][cur[1]]-count < 0) ? 0 : Map[cur[0]][cur[1]] - count; // for(int i = 0; i < Num; i++) // { // for(int j = 0; j < K; j++) // { // cout << Map[i][j]; // } // cout << endl; // } } } // int SearchIceberg(const vector>& Map, vector> visited) // { // int count = 0; // for(int i = 0; i < Num; i++) // { // for(int j = 0; j < K; j++) // { // if(Map[i][j] != 0 && !visited[i][j]) // { // SearchConnection(Map, visited, {i,j}); // count++; // } // } // } // return count; // } // int CountSeaSide(const vector>& Map, array pos) // { // array dir[4]; // int count = 0; // for(int i = 0; i<4; i++) // { // dir[i] = {pos[0]+dy[i], pos[1]+dx[i]}; //E,N,W,S // } // if(dir[0][1] < K && Map[dir[0][0]][dir[0][1]] == 0) count++; // if(dir[1][0] < Num && Map[dir[1][0]][dir[1][1]] == 0) count++; // if(dir[2][1] >= 0 && Map[dir[2][0]][dir[2][1]] == 0) count++; // if(dir[3][0] >= 0 && Map[dir[3][0]][dir[3][1]] == 0) count++; // return count; // } int Melting(vector>& Map) { int countIceberg = 0; vector> visited(Num,vector(K)); for(int i = 0; i < Num; i++) { for(int j = 0; j < K; j++) { if(Map[i][j] != 0) { if(!visited[i][j]) { SearchConnection(Map, visited, {i,j}); countIceberg++; } } } } return countIceberg; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> Num >> K; vector> Map(Num,vector(K)); // vector> Sea(Num,vector(K)); for(int i = 0; i < Num; i++) { for(int j = 0; j < K; j++) { cin >> Map[i][j]; } } // cout << "initial" << endl; // for(int i = 0; i < Num; i++) // { // for(int j = 0; j < K; j++) // { // cout << Map[i][j]; // } // cout << endl; // } int count = 0; int years = 0; while(count < 2) { count = Melting(Map); // cout << "after melting" << endl; // for(int i = 0; i < Num; i++) // { // for(int j = 0; j < K; j++) // { // cout << Map[i][j]; // } // cout << endl; // } if (count >= 2) break; // Melting(Map, Sea); years++; } cout << years << "\n"; return 0; }

제출 #75732

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: