QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#532685 | #9224. Express Eviction | MIT Isn’t Training (Jiangqi Dai, Ziqian Zhong, Peter Zhou)# | WA | 288ms | 7196kb | C++14 | 3.5kb | 2024-08-25 09:09:46 | 2024-08-25 09:09:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define SZ 200055
int h,w;
typedef pair<int,int> pii;
#define fi first
#define se second
char u[66][66];
void edt(set<pii>&s,pii u,int w) {
for(int dx=0;dx<=1;++dx)
for(int dy=0;dy<=1;++dy) {
pii o(u.fi+dx,u.se+dy);
if(w) s.insert(o); else s.erase(o);
}
}
int contb(vector<pii> a) {
set<pii> g;
edt(g,a.back(),1);
for(int i=0;i+1<a.size();++i)
edt(g,a[i],0);
int ans=0;
for(auto t:g)
// cout<<t.fi<<","<<t.se<<"JAA\n",
ans+=u[t.fi][t.se]=='#';
return ans;
}
const int dx[]={-1,1,0,0},dy[]={0,0,-1,1};
map<pii,pii> ff;
pii gf(pii t) {
return ff.count(t)?ff[t]=gf(ff[t]):t;
}
void dj(pii t) {
int ans=2e9;
map<pii,int> DD;
map<vector<pii>,int> d;
priority_queue<pair<int,vector<pii>>> q;
vector<pii> S{t}; int O=contb(S)+1;
d[S]=O; q.push({-O,S});
while(!q.empty()) {
auto t=q.top(); q.pop(); t.fi*=-1;
if(d[t.se]!=t.fi) continue;
for(int k=0;k<4;++k) {
pii tt(t.se.back().fi+dx[k],t.se.back().se+dy[k]);
if(tt.fi<0||tt.fi>h||tt.se<0||tt.se>w) continue;
auto TT=t.se; TT.push_back(tt); int EX=contb(TT);
if(TT.size()==4) TT.erase(TT.begin());
int&G=d[TT];
if(G!=0&&G<=t.fi+EX) continue;
G=t.fi+EX;
if(!DD.count(tt)||DD[tt]>G) DD[tt]=G;
if(tt.fi==h&&tt.se==w) ans=min(ans,G);
q.push({-G,TT});
}
for(int dx=-1;dx<=1;dx+=2)
for(int dy=-1;dy<=1;dy+=2) {
pii tt(t.se.back().fi+dx,t.se.back().se+dy);
if(tt.fi<0||tt.fi>h||tt.se<0||tt.se>w) continue;
bool GOOD=0;
for(int g=0;g<4;++g)
for(int h=0;h<4;++h) {
pii w(t.se.back().fi+::dx[g]*2,t.se.back().se+::dy[g]*2);
pii o(tt.fi+::dx[h]*2,tt.se+::dy[h]*2);
if(w.fi<0||w.fi>::h||w.se<0||w.se>::w) continue;
if(o.fi<0||o.fi>::h||o.se<0||o.se>::w) continue;
if(contb({w})==0&&contb({o})==0&&gf(w)==gf(o)) {
GOOD=1; goto GOO;
}
}
GOO:;
if(!GOOD) continue;
auto TT=t.se; TT.push_back(tt); int EX=contb(TT);
if(TT.size()==4) TT.erase(TT.begin());
int&G=d[TT];
if(G!=0&&G<=t.fi+EX) continue;
G=t.fi+EX;
if(!DD.count(tt)||DD[tt]>G) DD[tt]=G;
if(tt.fi==h&&tt.se==w) ans=min(ans,G);
q.push({-G,TT});
}
}
// cout<<contb({{2,0}})<<"?\n";
// cout<<contb({{1,0},{2,0},{3,0}})<<"?\n";
// cout<<contb({{2,0},{3,0}})<<"?\n";
cout<<ans-1<<"\n";
// for(int i=0;i<=h;++i,cout<<"\n")
// for(int j=0;j<=w;++j)
// cout<<DD[pii(i,j)]-1<<" ";
}
#define goo(x,y) (contb({pii(x,y)})==0)
int main() {
cin>>h>>w;
for(int i=1;i<=h;++i) cin>>(u[i]+1);
for(int i=0;i<=h;++i)
for(int j=0;j<=w;++j) if(goo(i,j)) {
for(int k=0;k<4;++k) {
int ii=dx[k]+i,jj=dy[k]+j;
if(ii>=0&&ii<=h&&jj>=0&&jj<=w&&goo(ii,jj)) {
pii t1(i,j),t2(ii,jj);
t1=gf(t1),t2=gf(t2);
if(t1!=t2) ff[t1]=t2;
}
}
}
dj({0,0});
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 6ms
memory: 3928kb
input:
4 6 .##... .#.... ##.... ....#.
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 100ms
memory: 5124kb
input:
20 30 ...########################### #..########################### ...########################### ...########################### .############################# ...########################### ...########################### #..########################### ...########################### ..#...............
output:
11
result:
ok 1 number(s): "11"
Test #3:
score: -100
Wrong Answer
time: 288ms
memory: 7196kb
input:
35 35 ....###########...#########........ ##..#######################..#####. ....#######################..#####. ...#.....##################..#####. .##......##################.....##. .##..##..#############.....#....##. .....##..#############......##..##. ....#....#############..##..##..##. ####.....
output:
21
result:
wrong answer 1st numbers differ - expected: '16', found: '21'