글 읽기 - 메모리초과가 왜 날까요 ..ᅮ

(追記) (追記ここまで)

메모리초과가 왜 날까요 ..ᅮ

2573번 - 빙산

jihoon7171 1년 전 0

우선 bfs( 얼음 갯수 세는 곳) 에서 나는걸로 추정하는데.. 도저히 모르겠습니다

#include <iostream>
#include <vector>
#include <climits>
#include <string>
#include <algorithm>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<limits.h>
#include<queue>
using namespace std;
int n,m;
vector<vector<int>>ice;
vector<vector<int>>checked;
const int dx[4] = {1,-1,0,0};
const int dy[4] = {0,0,1,-1};
void melting(){
 queue<pair<int, int>>q;
 for(int i=0;i<n;i++){
 for(int j=0;j<m;j++){
 if(ice[i][j]>0){
 q.push({j,i});
 }
 }
 }
 queue<pair<int, int>>pasteq(q);
 queue<int>minus;
 while(!pasteq.empty()){
 int x = pasteq.front().first;
 int y = pasteq.front().second;
 pasteq.pop();
 int count=0;
 for(int i=0;i<4;i++){
 int newx = x+dx[i];
 int newy = y+dy[i];
 if(newx>=0&&newx<m&&newy>=0&&newy<n){
 if(ice[newy][newx] == 0){
 count++;
 }
 }
 }
 minus.push(count);
 }
 while(!q.empty()){
 int x = q.front().first;
 int y = q.front().second;
 q.pop();
 int temp = minus.front();
 minus.pop();
 ice[y][x] -= temp;
 if(ice[y][x] < 0) ice[y][x] = 0;
 }
 
}
void bfs(vector<vector<bool>>&checking, int x, int y){
 queue<pair<int, int>>q;
 q.push({x,y});
 while(!q.empty()){
 int nowx = q.front().first;
 int nowy = q.front().second;
 checking[nowy][nowx] = true;
 q.pop();
 for(int i=0;i<4;i++){
 int newx = nowx+dx[i];
 int newy = nowy+dy[i];
 if(newx>=0&&newx<m&&newy>=0&&newy<n&&ice[newy][newx]>0&&!checking[newy][newx]){
 q.push({newx, newy});
 }
 }
 }
}
bool allzero(){
 for(int i=0;i<n;i++){
 for(int j=0;j<m;j++){
 if(ice[i][j] > 0){
 return false;
 }
 }
 }
 return true;
}
int main() {
 ios::sync_with_stdio(false);
 cin.tie(nullptr);
 cout.tie(nullptr);
 cin>>n>>m;
 ice.resize(n,vector<int>(m));
 for(int i=0;i<n;i++){
 for(int j=0;j<m;j++){
 cin>>ice[i][j];
 }
 }
 int count=0;
 while(1){
 count +=1;
 melting();
 // cout<<"\n";
 // for(int i=0;i<n;i++){
 // for(int j=0;j<m;j++){
 // cout<<ice[i][j]<<" ";
 // }
 // cout<<"\n";
 // }
 vector<vector<bool>>checking(n,vector<bool>(m,false));
 int piece =0;
 for(int i=0;i<n;i++){
 for(int j=0;j<m;j++){
 if(ice[i][j] > 0 && !checking[i][j]){
 piece +=1;
 bfs(checking, j, i);
 }
 }
 }
 if(piece>1) {cout<<count; break;}
 if(allzero()){ cout << 0; break;}
 }
}

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

메모리초과가 왜 날까요 ..ᅮ

jihoon7171 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말