搜索_2

· · 个人记录

P1479

这一题先考虑暴力爆搜。
总共有 5 \times 5 = 25 个格子，每个格子可以放，也可以不放，共有 2 ^ {25} = 33554432 种可能。和 1e8 差得远呢。
所以，考虑爆搜。

Code

当初怕爆时间，写了一个打表的代码，反正也就25个 

#include <iostream>
using namespace std;
int a[30] = {0,0,0,0,0,1,1,1,1,3,3,3,6,6,10,10,15,21,21,28,28,35,30,30,27,12};

int main(){
    int n;
    cin >> n;
    cout << a[n];
}

下面之我打表的代码，DFS，交上去就A了 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll n,ans; 
bool vis[10][10],t[15];

void dfs(int x,int y,int cnt){
    if(y > 5){
        dfs(x + 1,1,cnt);
        return ;
    }
    if(cnt > n){
        return ;
    }
    if(x == 6){
        if(cnt != n) return ;
        ll num = 0;
        if(vis[1][1] == 1 && vis[1][2] == 1 && vis[1][3] == 1 && vis[1][4] == 1 && vis[1][5] == 1) num++;
        if(vis[2][1] == 1 && vis[2][2] == 1 && vis[2][3] == 1 && vis[2][4] == 1 && vis[2][5] == 1) num++;
        if(vis[3][1] == 1 && vis[3][2] == 1 && vis[3][3] == 1 && vis[3][4] == 1 && vis[3][5] == 1) num++;
        if(vis[4][1] == 1 && vis[4][2] == 1 && vis[4][3] == 1 && vis[4][4] == 1 && vis[4][5] == 1) num++;
        if(vis[5][1] == 1 && vis[5][2] == 1 && vis[5][3] == 1 && vis[5][4] == 1 && vis[5][5] == 1) num++;
        if(vis[1][1] == 1 && vis[2][1] == 1 && vis[3][1] == 1 && vis[4][1] == 1 && vis[5][1] == 1) num++;
        if(vis[1][2] == 1 && vis[2][2] == 1 && vis[3][2] == 1 && vis[4][2] == 1 && vis[5][2] == 1) num++;
        if(vis[1][3] == 1 && vis[2][3] == 1 && vis[3][3] == 1 && vis[4][3] == 1 && vis[5][3] == 1) num++;
        if(vis[1][4] == 1 && vis[2][4] == 1 && vis[3][4] == 1 && vis[4][4] == 1 && vis[5][4] == 1) num++;
        if(vis[1][5] == 1 && vis[2][5] == 1 && vis[3][5] == 1 && vis[4][5] == 1 && vis[5][5] == 1) num++;
        if(vis[1][1] == 1 && vis[2][2] == 1 && vis[3][3] == 1 && vis[4][4] == 1 && vis[5][5] == 1) num++;
        if(vis[1][5] == 1 && vis[2][4] == 1 && vis[3][3] == 1 && vis[4][2] == 1 && vis[5][1] == 1) num++;
        if(t[num] == 0){
            t[num] = 1;
            ans += num;
        }
        return ;
    }
    dfs(x,y + 1,cnt);
    vis[x][y] = 1;
    dfs(x,y + 1,cnt + 1);
    vis[x][y] = 0;
}

int main(){
    cin >> n;
    dfs(1,1,0);
    cout << ans; 
    return 0;
}

P7012

这一题，还是考虑爆搜。

这是W在 (1,2) 时最多能放的棋子数量，爆搜后得到答案为12

所以可以考虑爆搜 ### Code ```cpp #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; ll n,m,ans; int vis[15][15]; int dx[5] = {0,2,-2,2,-2}; int dy[5] = {0,2,2,-2,-2}; void dfs(ll x,ll y,ll cnt){ ans = max(ans,cnt); for(int i = 1;i <= 4;i++){ ll nx = x + dx[i],ny = y + dy[i],ex = x + dx[i] / 2,ey = y + dy[i] / 2; if(nx >= 1 && nx <= n && ny >= 1 && ny <= m){ if(vis[nx][ny] == 0 && vis[ex][ey] == -1){ vis[ex][ey] = 0; dfs(nx,ny,cnt + 1); vis[ex][ey] = -1; } } } } void work(){ ans = 0; n = m = 10; for(int i = 1;i <= n;i++){ for(int j = 1;j <= m;j++){ char c; cin >> c; if(c == '.' || c == '#'){ vis[i][j] = 0; } if(c == 'B') vis[i][j] = -1; if(c == 'W') vis[i][j] = 1; } } for(int i = 1;i <= n;i++){ for(int j = 1;j <= m;j++){ if(vis[i][j] == 1){ vis[i][j] = 0; dfs(i,j,0); vis[i][j] = 1; } } } cout << ans << "\n"; } int main(){ ll T; cin >> T; while(T--) work(); return 0; } ``` ## [P1123](https://www.luogu.com.cn/problem/P1123) 仍然优先考虑爆搜。 所有的都填出来后，最多可选九个数 ![](https://cdn.luogu.com.cn/upload/image_hosting/rmyx9zu6.png) 在三十六个数中选九个数，一共有 $C^{9}_{36} = 94143280$ 种(不考虑相邻)，大约 $9e7$ ，乘上 $20$ 后为 $1.8e9$，考虑相邻就能剪掉大量的状态，所以可以通过 注意一个坑点，vis数组不能用bool，因为他可能被多个区域覆盖。 ### Code ```cpp #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; ll n,m,a[10][10],ans; int vis[10][10]; void dfs(int x,int y,ll cnt){ if(y > m){ dfs(x + 1,1,cnt); return ; } if(vis[x][y] >= 1){ dfs(x,y + 1,cnt); return ; } // cout << x << " " << y << "\n"; if(x > n){ ans = max(ans,cnt); return ; } vis[x][y]++; vis[x + 1][y]++; vis[x][y + 1]++; vis[x - 1][y]++; vis[x][y - 1]++; vis[x - 1][y - 1]++; vis[x - 1][y + 1]++; vis[x + 1][y - 1]++; vis[x + 1][y + 1]++; dfs(x,y + 1,cnt + a[x][y]); vis[x][y]--; vis[x + 1][y]--; vis[x][y + 1]--; vis[x - 1][y]--; vis[x][y - 1]--; vis[x - 1][y - 1]--; vis[x - 1][y + 1]--; vis[x + 1][y - 1]--; vis[x + 1][y + 1]--; dfs(x,y + 1,cnt); } void work(){ cin >> n >> m; for(int i = 1;i <= n;i++){ for(int j = 1;j <= m;j++){ cin >> a[i][j]; vis[i][j] = 0; ans = 0; } } for(int i = 0;i <= n + 1;i++){ for(int j = 0;j <= m + 1;j++){ vis[i][j] = 0; } } dfs(1,1,0); cout << ans << "\n"; return ; } int main(){ ll T; cin >> T; while(T--) work(); return 0; } ```