| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 840906 | 7mody | 축구 경기장 (IOI23_soccer) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<int>> row;
vector<vector<int>> col;
vector<vector<int>> arr;
int n;
bool check(int x1,int y1,int x2,int y2){
if(x1==x2) return (row[x1][y1] - row[x2][y2] == 0);
if(y1==y2) return (col[x1][y1] - col[x2][y2] == 0);
return ((row[x1][y1] - row[x1][y2] == 0 && col[x1][y2] - col[x2][y2] == 0) || (col[x1][y1] - col[x2][y1] == 0 && row[x2][y1] - row[x2][y2] == 0));
}
int biggest_stadium(int N, vector<vector<int>> F)
{
arr=F;
n=N;
int ans=0;
row=F;
col=F;
for(int i=0; i < n;i++){
for(int j=1; j < n;j++){
row[i][j]+=row[i][j-1];
col[j][i]+=col[j-1][i];
}
}
queue<pair<int,int>> q;
for(int i=0; i < n;i++){
for(int j=0; j < n;j++){
if(arr[i][j]) continue;
q.push({i-1,j});
q.push({i,j-1});
q.push({i+1,j});
q.push({i,j+1});
int curr=1;
vector<pair<int,int>> found;
vector<vector<bool>> vis(n,vector<bool>(n));
vis[i][j]=true;
found.push_back({i,j});
while(!q.empty()){
int x=q.front().first,y=q.front().second;
q.pop();
bool ok=true;
if(x==-1 || x==n || y==-1 || y==n || arr[x][y] || vis[x][y]) continue;
vis[x][y]=true;
for(pair<int,int> c : found){
if(!check(c.first,c.second, x , y)){
ok=false;
break;
}
}
if(!ok) continue;
found.push_back({x,y});
curr++;
// cout << curr << ' ' << x << ' ' << y << endl;
q.push({x-1,y});
q.push({x,y-1});
q.push({x+1,y});
q.push({x,y-1});
}
ans=max(ans,curr);
}
}
return ans;
}
void solve(){
int n; cin >> n;
vector<vector<int>> arr(n,vector<int>(n));
for(int i=0; i < n;i++){
for(int j=0; j < n;j++){
cin >> arr[i][j];
}
}
cout << biggest_stadium(n,arr) << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
int t=1;
cin >> t;
while(t--){
solve();
}
}