OJ 14502 : 연구소 - C++
연구소
코드
#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#define ll long long
#define ull unsigned long long
using namespace std;
// 06:37 ~ 07:10
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int N,M,ans;
int board[10][10];
int cpy[10][10];
bool vis[10][10];
vector<pair<int,int>> virus;
vector<pair<int,int>> zero;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(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] == 2)
virus.push_back({i,j});
else if(board[i][j] == 0)
zero.push_back({i,j});
}
}
int ch[zero.size()];
fill(ch, ch+zero.size(), 1);
for(int i=0;i<3;i++) ch[i] = 0;
do{
queue<pair<int,int>> q;
for(int i=0;i<N;i++)
{
fill(vis[i], vis[i]+M, false);
for(int j=0;j<M;j++)
cpy[i][j] = board[i][j];
}
for(int i=0;i<zero.size();i++)
if(ch[i] == 0)
cpy[zero[i].first][zero[i].second] = 1;
for(int i=0;i<virus.size();i++)
{
vis[virus[i].first][virus[i].second] = true;
q.push(virus[i]);
}
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(nx<0 or ny<0 or nx>=M or ny>=N) continue;
if(vis[ny][nx] or cpy[ny][nx] == 1) continue;
q.push({ny,nx});
vis[ny][nx] = true;
cpy[ny][nx] = 2;
}
}
/* 안전영역 검사 */
int cnt=0;
for(int i=0;i<N;i++)
for(int j=0;j<M;j++)
if(cpy[i][j] == 0) cnt++;
ans = max(ans, cnt);
}while(next_permutation(ch, ch+zero.size()));
cout << ans;
return 0;
}
- 로직
next_permutation()
으로 모든 '0' 좌표
중 3개를 선택
해서 '1'로 바꾸고
BFS
를 실행
'0'
카운드
하여 최대값 카운트
next_permutation()
이 없으면?
: 3-depth인 재귀
를 통해 3개의 '0'좌표
를 '1'
로 바꾼 뒤 BFS
수행!
Author And Source
이 문제에 관하여(OJ 14502 : 연구소 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/BOJ-14502-연구소-C
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#include <cstdio> #include <vector> #include <queue> #include <iostream> #include <cmath> #include <algorithm> #include <set> #include <deque> #include <numeric> #define ll long long #define ull unsigned long long using namespace std; // 06:37 ~ 07:10 int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; int N,M,ans; int board[10][10]; int cpy[10][10]; bool vis[10][10]; vector<pair<int,int>> virus; vector<pair<int,int>> zero; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(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] == 2) virus.push_back({i,j}); else if(board[i][j] == 0) zero.push_back({i,j}); } } int ch[zero.size()]; fill(ch, ch+zero.size(), 1); for(int i=0;i<3;i++) ch[i] = 0; do{ queue<pair<int,int>> q; for(int i=0;i<N;i++) { fill(vis[i], vis[i]+M, false); for(int j=0;j<M;j++) cpy[i][j] = board[i][j]; } for(int i=0;i<zero.size();i++) if(ch[i] == 0) cpy[zero[i].first][zero[i].second] = 1; for(int i=0;i<virus.size();i++) { vis[virus[i].first][virus[i].second] = true; q.push(virus[i]); } 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(nx<0 or ny<0 or nx>=M or ny>=N) continue; if(vis[ny][nx] or cpy[ny][nx] == 1) continue; q.push({ny,nx}); vis[ny][nx] = true; cpy[ny][nx] = 2; } } /* 안전영역 검사 */ int cnt=0; for(int i=0;i<N;i++) for(int j=0;j<M;j++) if(cpy[i][j] == 0) cnt++; ans = max(ans, cnt); }while(next_permutation(ch, ch+zero.size())); cout << ans; return 0; }
- 로직
next_permutation()
으로모든 '0' 좌표
중3개를 선택
해서'1'로 바꾸고
BFS
를 실행'0'
카운드
하여최대값 카운트
next_permutation()
이 없으면?
:3-depth인 재귀
를 통해3개의 '0'좌표
를'1'
로 바꾼 뒤BFS
수행!
Author And Source
이 문제에 관하여(OJ 14502 : 연구소 - C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/BOJ-14502-연구소-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)