1206. 剪格子

2021-02-15 ||13:47

受到y总优化思路的启发，结合我原有思路，比标程快了将近10倍。

y总优化思路：1411ms | 我的优化思路：1051ms |结合二者优化思路：162ms

最终代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=20,P=131;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int sum;
int ans=INT_MAX;
int n,m;
int val[N][N];
bool st[N][N];
bool ct[N][N];
unordered_set<unsigned long long> se;
vector<int>loc;
vector<int>los;
int cot;
int turn(int x,int y){
    return (x-1)*n+y;
}
bool bfs(int cnt){
    while(!loc.empty()){
        int si=loc.size()-1;
        int id=loc[si];
        int x=(id-1)/n+1,y=(id-1)%n+1;
        loc.pop_back();
        for(int i=0;i<4;i++){
            int a=x+dx[i],b=y+dy[i];
            if(a<1||b<1||a>m||b>n)continue ;
            if(ct[a][b]==true)continue;
            cot++;
            loc.insert(loc.begin(),turn(a,b));
            ct[a][b]=true;
        }
    }
    if(cot==m*n-cnt)return true;
    return false;
}
bool check(vector <int>u){
    sort(u.begin(),u.end());
    unsigned long long x = 0;
    for (int i = 0; i < u.size(); i ++ ){
        x=x*P+(u[i]-1)/n+1;
        x=x*P+(u[i]-1)%n+1;
    }
    if (se.count(x)) {
        return true;
    }
    se.insert(x);
    return false;
}
bool cmp(int a,int b){
    return b<a;
}
void dfs(int cnt,int v,vector<int>lo){
     if(v==sum/2){
       cot=0;
       memcpy(ct,st,sizeof st);
       for(int i=1;i<=m;i++){
         if(loc.size())break;
           for(int j=1;j<=n;j++){
              if(ct[i][j]==false){
                  loc.push_back(turn(i,j));
                  cot++;
                  ct[i][j]=true;
                  break;
              }
           }
        }
       if(bfs(cnt)==true){
         ans=min(ans,cnt);
        }
        return;
    }
    if(v>=sum/2)return;
    if(cnt==m*n)return;
    if(check(lo))return;
    bool fr[200];
    memset(fr,false,sizeof fr);
    int len=lo.size();
    vector<int>bkt;
    bkt.clear();
    for(int k=0;k<len;k++){
        int p=lo[k];
        int x=(p-1)/n+1,y=(p-1)%n+1;
        fr[turn(x,y)]=true;
            for(int i=0;i<4;i++){
                int a=x+dx[i],b=y+dy[i];
                if(a<1||b<1||a>m||b>n)continue;
                if(st[a][b]==true)continue;
                if(fr[turn(a,b)]==true)continue;
                if(cnt+1>=ans)continue;
                fr[turn(a,b)]=true;
                bkt.push_back(turn(a,b));
            }
    }
    sort(bkt.begin(),bkt.end(),cmp);
    for(int i=0;i<bkt.size();i++){
        lo.push_back(bkt[i]);
        int x=(bkt[i]-1)/n+1,y=(bkt[i]-1)%n+1;
        st[x][y] = true;
        dfs(cnt+1,v+val[x][y], lo);
        lo.pop_back();
        st[x][y] = false;
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&val[i][j]);
            sum+=val[i][j];
        }
    }
    if(sum%2==0){
        st[1][1]=true;
        los.push_back(turn(1,1));
        dfs(1,val[1][1],los);
    }
    printf("%d",ans==INT_MAX?0:ans);
    return 0;
}

2021-02-15||13:11

蓝桥杯官网数据早早地过了，y总成功以一己之力提高了本题档次。

艰难地摸索正确解法，优化剪枝，写了一个上午。

#include<bits/stdc++.h>
using namespace std;
const int N=20,P=131;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int sum;
int ans=INT_MAX;
int n,m;
int val[N][N];
bool st[N][N];
bool ct[N][N];
unordered_set<unsigned long long> se;
vector<int>loc;
vector<int>los;
int cot;
int turn(int x,int y){
    return (x-1)*n+y;
}
bool bfs(int cnt){
    while(!loc.empty()){
        int si=loc.size()-1;
        int id=loc[si];
        int x=(id-1)/n+1,y=(id-1)%n+1;
        loc.pop_back();
        for(int i=0;i<4;i++){
            int a=x+dx[i],b=y+dy[i];
            if(a<1||b<1||a>m||b>n)continue ;
            if(ct[a][b]==true)continue;
            cot++;
            loc.insert(loc.begin(),turn(a,b));
            ct[a][b]=true;
        }
    }
    if(cot==m*n-cnt)return true;
    return false;
}
bool check(vector <int>u){
    sort(u.begin(),u.end());
    unsigned long long x = 0;
    for (int i = 0; i < u.size(); i ++ ){
        x=x*P+(u[i]-1)/n+1;
        x=x*P+(u[i]-1)%n+1;
    }
    if (se.count(x)) {
        return true;
    }
    se.insert(x);
    return false;
}
void dfs(int cnt,int v,vector<int>lo){
     if(v==sum/2){
       cot=0;
       memcpy(ct,st,sizeof st);
       for(int i=1;i<=m;i++){
         if(loc.size())break;
           for(int j=1;j<=n;j++){
              if(ct[i][j]==false){
                  loc.push_back(turn(i,j));
                  cot++;
                  ct[i][j]=true;
                  break;
              }
           }

       }
       if(bfs(cnt)==true){
         ans=min(ans,cnt);
        }
        return;
    }
    if(v>=sum/2)return;
    if(cnt==m*n)return;
    if(check(lo))return;
    bool fr[200];
    memset(fr,false,sizeof fr);
    int len=lo.size();
    for(int k=0;k<len;k++){
        int p=lo[k];
        int x=(p-1)/n+1,y=(p-1)%n+1;
        fr[turn(x,y)]=true;
            for(int i=0;i<4;i++){
                int a=x+dx[i],b=y+dy[i];
                if(a<1||b<1||a>m||b>n)continue;
                if(st[a][b]==true)continue;
                if(fr[turn(a,b)]==true)continue;
                if(cnt+1>=ans)continue;
                st[a][b]=true;
                fr[turn(a,b)]=true;
                lo.push_back(turn(a,b));
                dfs(cnt+1,v+val[a][b],lo);
                lo.pop_back();
                st[a][b]=false;
            }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&val[i][j]);
            sum+=val[i][j];
        }
    }
    if(sum%2==0){
        st[1][1]=true;
        los.push_back(turn(1,1));
        dfs(1,val[1][1],los);
    }
    printf("%d",ans==INT_MAX?0:ans);
    return 0;
}