QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#532685#9224. Express EvictionMIT Isn’t Training (Jiangqi Dai, Ziqian Zhong, Peter Zhou)#WA 288ms7196kbC++143.5kb2024-08-25 09:09:462024-08-25 09:09:48

Judging History

你现在查看的是最新测评结果

  • [2024-08-25 09:09:48]
  • 评测
  • 测评结果:WA
  • 用时:288ms
  • 内存:7196kb
  • [2024-08-25 09:09:46]
  • 提交

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'