| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 995777 | aaaaaarroz | 축구 경기장 (IOI23_soccer) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
bool limites(int N, int i, int j){
return i>=0&&i<N&&j>=0&&j<N;
}
int biggest_stadium(int N, vector<vector<int>> F){
if(N>30){
int empty_cells=0;
bool posible=true;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(F[i][j]==0){
empty_cells++;
}
else{
int grado=0;
for(int ii=0;ii<4;ii++){
if(limites(N,i+dx[ii],j+dy[ii])){
if(F[i+dx[ii]][j+dy[ii]]==0){
grado++;
}
}
}
if(grado>=3){
posible=false;
}
}
}
}
return posible==true?empty_cells:1;
}
int empty_cells=0;
pair<int,int>arbol;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(F[i][j]==0){
empty_cells++;
}
}
}
bool si=true;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(F[i][j]==1){
continue;
}
priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>>cola;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
vector<vector<int>>dist(N,vector<int>(N,-1));
dist[i][j]=0;
cola.push({0,i,j});
while(!cola.empty()){
auto[d,x,y]=cola.top();
cola.pop();
for(int dir=0;dir<4;dir++){
int posi=x+dx[dir];
int posj=y+dy[dir];
while(true){
if((d+1)<dist[posi][posj]){
dist[posi][posj]=d+1;
cola.push({dist[posi][posj],posi,posj});
posi+=dx[dir];
posj+=dy[dir];
}
}
}
}
for(int x=0;x<N;x++){
for(int y=0;y<N;y++){
if(F[x][y]==0&&(dist[x][y]>=3||dist[x][y]==-1)){
si=false;
}
}
}
if(!si){
break;
}
}
if(!si){
break;
}
}
if(si){
return empty_cells;
}
else{
return 1;
}
}
int main()
{
int N;
cin>>N;
vector<std::vector<int>> F(N, vector<int>(N));
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin>>F[i][j];
}
}
int res = biggest_stadium(N, F);
cout<<res<<"\n";
return 0;
}