题解：P3053 [USACO12OPEN] Unlocking Blocks S

wleagle · 2024-08-08 12:58:28 · 题解

P3053 [USACO12OPEN] Unlocking Blocks S （DFS剪枝）

题意

在 0 到 9 的 10 \times 10 方格内给出 3 个由小正方形拼出的块。这些块每次只能够上下左右移动 1 格，不能重叠。问最小需要多少步才能让 3 个块所在的最小矩形互不重叠。

解题思路

前两篇题解都是 BFS，因为每个块每步只有四个移动方向，而总移动步数直观的感觉就比较小，所以用自然就能想到用广搜找到第一个解即可。而如果用 DFS，总的状态空间随着步数是指数增长的，并且要遍历所有状态才能找到最短的解决办法，显然不是首选算法。但作为一个执（犟）着（种）的人，非要用深搜来写写看。

基本考虑

和其它题解类似，由于没有绝对坐标会出现负数，以及三个块会一起跑的问题，所以让一个块坐标不变，当需要让这个块移动，就让另外两个一起反向移动，效果一样。形状的重叠判断遍历一下就好，矩形的重叠用长宽和位置算一下就好。这些其它题解都说了，不赘述。

剪枝优化

DFS 既然要遍历，就需要充分剪枝：

迭代过程中到达同一个状态，如果步数等于或大于当前记录的步数就返回。（基本操作）
每个块的总步数不能超过 9，因为如果原来两个块在某个方向有 10 的重叠，那它们就不可能在另一个方向也有 10 的重叠，否则形状就重叠了。（几何约束）
每个块所在矩形与不动的那个块，坐标差距不能超过 10，因为最终状态三个矩形一定是紧贴的（最小步数）。

代码

#include <bits/stdc++.h>
using namespace std;

int n[4], dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}, ans = INT_MAX;
int iter;

struct block{
    vector<pair<int,int>>p;  // 每个点坐标
    int ox, oy, wid, hei;  // 所在矩形左下角坐标和宽、高
}blks[4];

int hashpos(int t1, int t2){  // 离散每个坐标
    return (t1 + 50)*100 + (t2 + 50);
}

int hashstat(){    // 离散2、3和1的相对位置，表示三个块的位置状态
    int ret = 0;
    ret += blks[2].ox - blks[1].ox + 50; 
    ret += (blks[2].oy - blks[1].oy + 50)*100;
    ret += (blks[3].ox - blks[1].ox + 50)*10000;
    ret += (blks[3].oy - blks[1].oy + 50)*1000000;
    return ret;
}

unordered_map<int, int> mp;  //记录实际形状所占据位置
unordered_map<int, int>vis;  //记录状态是否达到过，以及达到的步数

int check(int i, int dir){  // 判断形状能否移动
    bool flag = true;
    for(auto tp : blks[i].p){
        int newx = tp.first + dx[dir];
        int newy = tp.second + dy[dir];
        if(mp[hashpos(newx, newy)] && mp[hashpos(newx, newy)] != i){ // 看看新位置有没有被占据
            flag = false;
        }
    }
    return flag;
}

int check2(int dir){  // 判断2个形状一起能否移动 
    bool flag = true;
    for(auto tp : blks[2].p){
        int newx = tp.first + dx[dir];
        int newy = tp.second + dy[dir];
        if(mp[hashpos(newx, newy)] && mp[hashpos(newx, newy)] == 1){ // 看看2的新位置是否与1冲突
            flag = false;
        }
    }
    for(auto tp : blks[3].p){
        int newx = tp.first + dx[dir];
        int newy = tp.second + dy[dir];
        if(mp[hashpos(newx, newy)] && mp[hashpos(newx, newy)] == 1){ // 看看3的新位置是否与1冲突
            flag = false;
        }
    }
    return flag;
}

void mov(int i, int dir){  // 移动形状
    int tmp[100][100];
    memset(tmp, 0, sizeof(tmp));
    for(auto &tp : blks[i].p){
        if(!tmp[tp.first + 50][tp.second + 50])
            mp[hashpos(tp.first, tp.second)] = 0;
        tp.first += dx[dir];
        tp.second += dy[dir];
        mp[hashpos(tp.first, tp.second)] = i;
        tmp[tp.first + 50][tp.second + 50] = true; // 移动的新位置，不会被改零
    }
    blks[i].ox += dx[dir]; // 更新定位坐标
    blks[i].oy += dy[dir];
    return;
}

void mov2(int dir){  // 移动2,3
    int tmp[100][100];
    memset(tmp, 0, sizeof(tmp));
    for(auto &tp : blks[2].p){
        if(!tmp[tp.first + 50][tp.second + 50])
            mp[hashpos(tp.first, tp.second)] = 0;
        tp.first += dx[dir];
        tp.second += dy[dir];
        mp[hashpos(tp.first, tp.second)] = 2;
        tmp[tp.first + 50][tp.second + 50] = true; // 移动的新位置，不会被改零
    }
    for(auto &tp : blks[3].p){
        if(!tmp[tp.first + 50][tp.second + 50])
            mp[hashpos(tp.first, tp.second)] = 0;
        tp.first += dx[dir];
        tp.second += dy[dir];
        mp[hashpos(tp.first, tp.second)] = 3;
        tmp[tp.first + 50][tp.second + 50] = true; // 移动的新位置，不会被改零
    }
    blks[2].ox += dx[dir]; // 更新定位坐标
    blks[2].oy += dy[dir];
    blks[3].ox += dx[dir]; 
    blks[3].oy += dy[dir];
    return;
}

bool checkov(){  // 检查矩形是否无重叠
    bool ret = true;
    for(int i = 1; i <= 3; i ++){
        int nexti = i + 1 > 3? i - 2: i + 1;
        ret = (blks[i].ox > blks[nexti].ox ? blks[i].ox - blks[nexti].ox >= blks[nexti].wid : blks[nexti].ox - blks[i].ox >= blks[i].wid) || 
        (blks[i].oy > blks[nexti].oy ? blks[i].oy - blks[nexti].oy >= blks[nexti].hei : blks[nexti].oy - blks[i].oy >= blks[i].hei);
        if(!ret) return false;
    }
    return ret;
}

void dfs(int x1, int x2, int x3){  // 参数为每个块移动的步数
    if(x1 + x2 + x3 >= ans || x1 > 9 || x2 > 9 || x3 > 9) return;  //  大于等于已有结果就剪枝，每个块移动不超过9步，总数不超过9步。
    if(vis[hashstat()] && x1 + x2 + x3 >= vis[hashstat()]){   
        return;  // 如果有过同样相对位置，并且步数更大，舍弃
    }else{
        vis[hashstat()] = x1 + x2 + x3;
    }
    if(abs(blks[2].ox - blks[1].ox) > 10 || abs(blks[2].oy - blks[1].oy) > 10 ||
        abs(blks[3].ox - blks[1].ox) > 10 || abs(blks[3].oy - blks[1].oy) > 10 ) 
        return;  // 如果和1号坐标差大于10，舍弃
    if(checkov()){
        ans = min(ans, x1 + x2 + x3); // 更新ans
        return;
    }
    for(int i = 1; i <= 3; i++){
        for(int dir = 0; dir < 4; dir++){
            int cdir = (dir + 2 > 3? dir - 2: dir + 2); //反向
            if(i == 1){  // 1号不动，反向移动两个，固定1号确保三个不会一起跑
                if(check2(cdir)){
                    mov2(cdir);
                    dfs(x1 + 1, x2, x3);
                    mov2(dir);
                }
            }else{
                if(check(i, dir)){
                    mov(i, dir);
                    dfs(x1, x2 + (i == 2), x3 + (i == 3));
                    mov(i, cdir);
                }
            }
        }
    }
    return;
}

int main() {
    cin >> n[1] >> n[2] >> n[3];
    for(int i = 1; i <= 3; i++){
        int minx = INT_MAX, miny = INT_MAX, maxx = 0, maxy = 0;
        for(int j = 1 ; j <= n[i]; j++){
            int rx, ry;
            cin >> rx >> ry;
            blks[i].p.push_back({rx, ry});
            minx = min(minx, rx);
            miny = min(miny, ry);
            maxx = max(maxx, rx);
            maxy = max(maxy, ry);
            mp[hashpos(rx, ry)] = i;
        }
        blks[i].ox = minx;
        blks[i].oy = miny;
        blks[i].wid = maxx - minx + 1;
        blks[i].hei = maxy - miny + 1;
    }
    dfs(0, 0, 0);
    if(ans == INT_MAX) cout << "-1";
    else cout << ans;
    return 0;
}