QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#486701 | #4520. Fence / Fox and Goose | inksamurai | RE | 0ms | 0kb | C++23 | 3.0kb | 2024-07-21 23:15:01 | 2024-07-21 23:15:02 |
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int) a.size()
#define all(a) a.begin(),a.end()
#define vec(...) vector<__VA_ARGS__>
#define _3Wcdivh ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
const int inf=1e9;
int n,m;
void slv(){
vec(string) a(n);
rep(i,n){
cin>>a[i];
}
int mi_i=n,ma_i=-1;
rep(i,n){
rep(j,m){
if(a[i][j]=='O'){
mi_i=min(mi_i,i);
ma_i=max(ma_i,i);
}
}
}
int mi_j=m,ma_j=0;
rng(i,mi_i,ma_i+1){
rep(j,m){
if(a[i][j]=='O'){
ma_j=max(ma_j,j);
mi_j=min(mi_j,j);
}
}
}
vi qsr(m,-1);
{
int now=0;
rng(i,mi_i,ma_i+1){
rep(j,m){
if(a[i][j]=='O'){
now=max(now,j);
}
}
qsr[i]=now;
}
now=0;
per(i,ma_i+1){
if(i<mi_i) break;
rep(j,m){
if(a[i][j]=='O'){
now=max(now,j);
}
}
if(now==ma_j) break;
qsr[i]=now;
}
}
vi qsl(m,m);
{
int now=m;
rng(i,mi_i,ma_i+1){
rep(j,m){
if(a[i][j]=='O'){
now=min(now,j);
}
}
qsl[i]=now;
}
now=m;
per(i,ma_i+1){
if(i<mi_i) break;
rep(j,m){
if(a[i][j]=='O'){
now=min(now,j);
}
}
if(now==mi_j) break;
qsl[i]=now;
}
}
int ans=0;
ans+=(ma_i-mi_i+1)*2+(ma_j-mi_j+1)*2;
vec(vi) usd(n,vi(m));
rng(i,mi_i,ma_i+1){
// print(qsl[i],qsr[i]);
rng(j,qsl[i],qsr[i]+1){
usd[i][j]=1;
}
}
pii p{-1,-1};
rep(i,n){
rep(j,m){
if(a[i][j]=='X'){
p={i,j};
}
}
}
assert(p!=pii(-1,-1));
// rep(i,n){
// rep(j,m){
// cout<<usd[i][j];
// }
// print();
// }
// print();
if(!usd[p.fi][p.se]){
cout<<ans<<"\n";
}else if(mi_i==ma_i or mi_j==ma_j){
if(n==1 or m==1){
cout<<"-1\n";
}else{
cout<<ans+4<<"\n";
}
}else{
ans+=2;
const int di[]={1,-1,0,0};
const int dj[]={0,0,1,-1};
auto ok=[&](int i,int j)->int{
return min(i,j)>=0 and i<n and j<m;
};
int val=inf;
vec(vi) dist(n,vi(m,-1));
dist[p.fi][p.se]=0;
queue<pii> que;
que.push({p.fi,p.se});
while(sz(que)){
auto [i,j]=que.front();
que.pop();
if(!usd[i][j]){
val=min(val,dist[i][j]);
}
rep(dir,4){
int ni=i+di[dir],nj=j+dj[dir];
if(!ok(ni,nj)){
val=min(val,dist[i][j]);
}else if(a[ni][nj]!='O'){
if(dist[ni][nj]==-1){
if(!usd[ni][nj]){
val=min(val,dist[i][j]);
}
dist[ni][nj]=dist[i][j]+1;
que.push({ni,nj});
}
}
}
}
if(val==inf){
cout<<"-1\n";
return;
}
val*=2;
ans+=val;
cout<<ans<<"\n";
}
}
signed main(){
_3Wcdivh;
while(cin>>n>>m){
slv();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
1 3 OXO 2 3 OXO ... 3 1 O X O 3 2 O. X. O. 6 3 O.X OOO O.O OOO OOO OOO 7 3 ..O ... ..X ... ... ... ... 6 7 ..OOOOO O..OOOO O..OOOO ....OO. ....XOO OOOOOOO 2 5 OOOX. O.OOO 2 9 O..OOXOOO OOO.OOOOO 8 1 O . . X . . O O 3 6 ...OO. .XOO.O OOO.OO 4 6 .O.OOO OX.... OO..OO O...OO 5 1 X O O . O 8 1 . . . O . ...