BOJ:2573氷山(C++)
質問する
コード#コード# #include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
int board[302][302];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int N,M;
bool checkTwice(){
int vis[N][M],cnt=0;
queue<pair<int,int>> cq;
for(int i=0;i<N;i++) fill(vis[i], vis[i]+M, 0);
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
if(vis[i][j] || board[i][j] == 0) continue;
cq.push({i,j});
vis[i][j] = 1;
cnt++;
while(!cq.empty())
{
auto cur = cq.front(); cq.pop();
for(int dir=0;dir<4;dir++)
{
int ny = cur.first + dy[dir];
int nx = cur.second + dx[dir];
if(ny < 0 || nx <0 || ny >=N || nx>= M) continue;
if(vis[ny][nx] || board[ny][nx] == 0) continue;
cq.push({ny,nx});
vis[ny][nx] = 1;
}
}
}
}
if(cnt >= 2) return true;
else return false;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
queue<pair<int,int>> q;
int day=0;
cin >> N >> M;
for(int i=0;i<N;i++)
for(int j=0;j<M;j++){
cin >> board[i][j];
if(board[i][j] > 0) q.push({i,j});
}
while(true)
{
day++;
int temp[302][302];
/* 임시 보드 temp에 board를 복사! */
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
temp[i][j] = board[i][j];
while(!q.empty())
{
auto cur = q.front(); q.pop();
for(int dir=0;dir<4;dir++)
{
int ny = cur.first + dy[dir];
int nx = cur.second + dx[dir];
if(ny < 0 || nx <0 || ny >=N || nx>= M) continue;
/* 비교는 board로 해야한다 */
if(board[ny][nx] > 0) continue;
/* 값 감소는 temp로 해야한다 */
if(temp[cur.first][cur.second] >0) temp[cur.first][cur.second] -=1;
}
}
/* 변경된 보드인 temp를 실제값인 board에 복사! */
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
board[i][j] = temp[i][j];
/* 녹지 않은 빙하위치를 찾기 위한 과정 */
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
if(board[i][j] > 0) q.push({i,j});
if(checkTwice()) break;
if(q.size() == 0){
day = 0;
break;
}
}
cout << day;
return 0;
}
#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
int board[302][302];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int N,M;
bool checkTwice(){
int vis[N][M],cnt=0;
queue<pair<int,int>> cq;
for(int i=0;i<N;i++) fill(vis[i], vis[i]+M, 0);
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
if(vis[i][j] || board[i][j] == 0) continue;
cq.push({i,j});
vis[i][j] = 1;
cnt++;
while(!cq.empty())
{
auto cur = cq.front(); cq.pop();
for(int dir=0;dir<4;dir++)
{
int ny = cur.first + dy[dir];
int nx = cur.second + dx[dir];
if(ny < 0 || nx <0 || ny >=N || nx>= M) continue;
if(vis[ny][nx] || board[ny][nx] == 0) continue;
cq.push({ny,nx});
vis[ny][nx] = 1;
}
}
}
}
if(cnt >= 2) return true;
else return false;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
queue<pair<int,int>> q;
int day=0;
cin >> N >> M;
for(int i=0;i<N;i++)
for(int j=0;j<M;j++){
cin >> board[i][j];
if(board[i][j] > 0) q.push({i,j});
}
while(true)
{
day++;
int temp[302][302];
/* 임시 보드 temp에 board를 복사! */
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
temp[i][j] = board[i][j];
while(!q.empty())
{
auto cur = q.front(); q.pop();
for(int dir=0;dir<4;dir++)
{
int ny = cur.first + dy[dir];
int nx = cur.second + dx[dir];
if(ny < 0 || nx <0 || ny >=N || nx>= M) continue;
/* 비교는 board로 해야한다 */
if(board[ny][nx] > 0) continue;
/* 값 감소는 temp로 해야한다 */
if(temp[cur.first][cur.second] >0) temp[cur.first][cur.second] -=1;
}
}
/* 변경된 보드인 temp를 실제값인 board에 복사! */
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
board[i][j] = temp[i][j];
/* 녹지 않은 빙하위치를 찾기 위한 과정 */
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
if(board[i][j] > 0) q.push({i,j});
if(checkTwice()) break;
if(q.size() == 0){
day = 0;
break;
}
}
cout << day;
return 0;
}
1)氷河の位置で4部屋をチェックして周りを減らして海(0)!
2)減少の過程で、リアルタイムで取締役会に値を反映できない
-->同じ年に一緒に溶けた氷河ですが、リアルタイムで変更すると
隣の氷河が溶けた後、次の氷河を計算すると、海の面積が増えました!
3)コピーボードがコア!
Reference
この問題について(BOJ:2573氷山(C++)), 我々は、より多くの情報をここで見つけました https://velog.io/@neity16/BOJ-2573-빙산-Cテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol