QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#486709 | #4520. Fence / Fox and Goose | inksamurai | AC ✓ | 40ms | 8952kb | C++23 | 3.0kb | 2024-07-21 23:19:14 | 2024-07-21 23:19:17 |
Judging History
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(n,-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;
}
}
// rng(i,mi_i,ma_i+1){
// print(qsr[i]);
// }
vi qsl(n,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();
}
}
详细
Test #1:
score: 100
Accepted
time: 40ms
memory: 8952kb
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 . ...
output:
-1 12 -1 12 18 4 36 14 24 -1 18 26 10 10 4 32 4 34 -1 18 14 18 40 24 -1 24 14 30 32 16 28 40 18 -1 20 8 4 12 38 6 4 30 -1 22 -1 12 28 -1 30 10 4 24 12 22 -1 36 6 -1 32 28 18 20 26 14 -1 36 20 16 14 32 22 4 30 -1 -1 14 38 -1 14 -1 26 24 22 8 -1 16 32 16 16 26 40 18 22 4 6 6 18 18 -1 16 30 30 34 30 -1...
result:
ok 114 lines