P1671 ------- 暴力搜索

MoonCake2011 · 2023-08-02 21:54:39 · 题解

我们用 dfs 找连通块。

每次将选过的坐标进行扩散，所以我们要记录每次选过的坐标。

选了 7 格后，将那 7 个坐标的 hash 值存入数组里。

对那个数组去重。

最终那个数组里的非重复个数就是答案。

记得用 vis 数组标记。

竟然能在 150ms 内卡过，时间总和才不到 710ms。

代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int d[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
bool vis[10][10];
char a[10][10];
bool check(int x,int y){
    return (x>0 && y>0 && x<=5 && y<=5);
}
vector<pair<int,int> >v;
struct node{
    pair<int,int>a[9];
    node(){
        for(int i=0;i<7;i++)
            a[i].first=a[i].second=0;
    }
    pair<int,int> &operator [] (int i){
        return a[i];
    }
    void Sort(){
        std::sort(a,a+7);
    }
    int get_hash(){
        int base=7,ans=0;
        for(int i=0;i<7;i++){
            ans=ans*base+a[i].first;
            ans=ans*base+a[i].second;
        }
        return ans;
    }
};
vector<int>ans;
void dfs(int x,int y,int cnt,int p){
    v.push_back({x,y});
    if(p==7){
        if(cnt>3){
            node x=node();
            for(int i=0;i<7;i++)
                x[i]=v[i];
            x.Sort();
            ans.push_back(x.get_hash());
        }
        v.pop_back();
        return;
    }
    vis[x][y]=1;
    for(int i=0;i<v.size();i++){
        int ux=v[i].first,uy=v[i].second;
        for(int j=0;j<4;j++){
            int tx=ux+d[j][0],ty=uy+d[j][1];
            if(!vis[tx][ty] && check(tx,ty))
                dfs(tx,ty,cnt+(a[tx][ty]=='J'),p+1);
        }
    }
    v.pop_back();
    vis[x][y]=0;
}
void read(){
    for(int i=1;i<=5;i++)
        for(int j=1;j<=5;j++)
            cin>>a[i][j];
}
signed main() {
    read();
    for(int i=1;i<=5;i++)
        for(int j=1;j<=5;j++)
            dfs(i,j,a[i][j]=='J',1);
    sort(ans.begin(),ans.end());
    int p=unique(ans.begin(),ans.end())-ans.begin();
    cout<<p;
    return 0;
}