搜索刷题计划与题解1（普及与普及-）

搜索做题笔记1

前言：很基础的爆搜，只给出几道有意义的题目链接和code,有些题目过于简单，就不给链接和代码了。题目一:P1036 全排列的升级版，双倍经验~题目二：P1141题目三：P1162题目四： P5198题目五：P2360题目六：P1464难度分割线~题目七：P1019 单词接龙
全新的搜索做题计划~ 1.24~1.29

从简单题开始~

AC code:
一种是把搜索状态表现出来，一种直接递归，code1：

void dfs(int u)
{
    if(cnt==k)
    {
        int sum = 0;
        for(int i = 0;i 
code2:
 
void dfs(int u,int sum,int cnt)
{
    // cout< 
题目二：P1141 
01迷宫那道题需要记录一下连通块的颜色，然后每次询问的时候看是否已经染色，对于每种颜色记录连通块的数量，没有染色的话还需要再bfs，染色了的话直接返回答案即可，但是还有wa点，不知道为什么
 
题目三：P1162 
填涂颜色：可以在最外圈加一层0，然后爆搜即可，属于小trick，我有时候也把dist数组用来记录染色或者标记，有时作为距离数组
 P1162
 AC code:
 
#include
using namespace std;
const int N = 35;
int a[N][N];
typedef pair PII;
PII q[N*N];
int n,m;
int cnt = 2;
int dist[N][N];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
void bfs(int sx,int sy)
{
    dist[sx][sy] = cnt;
    int hh = 0,tt = -1;
    q[++tt] = {sx,sy};
    while(hh<=tt)
    {
        auto t = q[hh++];
        dist[t.first][t.second] = cnt;
        for(int i = 0;i<4;i++)
        {
            int nx = dx[i]+t.first,ny = dy[i]+t.second;
            if(dist[nx][ny]) continue;
            if(a[nx][ny]==1)continue;
            if(nx<0||ny<0||nx>n+2||ny>n+2) continue;
            dist[nx][ny] = cnt;
            q[++tt] = {nx,ny};
        }
    }
}
int main()
{
    memset(dist,0,sizeof dist);
    cin>>n;
    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<=n;j++)
        {
            cin>>a[i][j];
            if(a[i][j]==1)
                dist[i][j] = 1;
        }
    }
    bfs(0,0);
    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<=n;j++)
        {
            if(dist[i][j]==2)
            {
                cout<<"0 ";
            }
            if(dist[i][j]==0)
            {
                cout<<"2 ";
            }
            if(dist[i][j]==1)
            {
                cout<<"1 ";
            }
        }
        cout< 
题目四： P5198 
P5198
 记录最大的冰淇淋面积即统计’#‘的连通块最大为多少，记录周长就看它的每个’#‘号旁边的’.‘的个数，注意’.'可能被重复计数，1~4次,这是蒟蒻第一次1A的普及难度的题呜呜呜
 AC code:
 
#include
#include
#include

using namespace std;
const int N = 1010;
char a[N][N],b[N][N];
typedef pair PII;
vectorans;
PII q[N*N];
bool st[N][N];
int n,m,sx,sy;
int cnt = 2;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
void bfs(int sx,int sy)
{
    int ss = 0,cc = 0;//面积，周长
    int hh = 0,tt = -1;
    q[++tt] = {sx,sy};
    st[sx][sy] = true;
    int cnt = 0;
    while(hh<=tt)
    {
        ss++;
        auto t = q[hh++];
        for(int i = 0;i<4;i++)
        {
            int nx = dx[i]+t.first,ny = dy[i]+t.second;
            if(st[nx][ny]) continue;
            if(b[nx][ny]=='.')
            {
                cc++;
                continue;
            }
            if(nx<=0||ny<=0||nx>n||ny>n) continue;
            st[nx][ny] = true;
            q[++tt] = {nx,ny};
        }
    }
    ans.push_back({ss,cc});
}
int main()
{
    cin>>n;
    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<=n;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i = 0;i<=n+1;i++)
    {
        for(int j = 0;j<=n+1;j++)
        {
            if(i==0||j==0||i==n+1||j==n+1)
            {
                b[i][j] = '.';
            }
            else
            {
                b[i][j] = a[i][j];
            }
        }
    }
    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<=n;j++)
        {
            if(b[i][j]=='#'&&!st[i][j])
            {
                bfs(i,j);
            }
        }
    }
    int s = -1e9,c = 1e9;
    sort(ans.begin(),ans.end());
    for(int i = ans.size()-1;i>=0;i--)
    {
        if(s<=ans[i].first)
        {
            s = ans[i].first;
            c = min(c,ans[i].second);
        }
    }
    cout< 
明日更新P1464 P2372 P2360 P1019 P1025~
 新的一天啦！
 
题目五：P2360 
P2360 
 三维的一个bfs，其实加一个第三维的数组以便于移动即可，但是需要注意使用pair就不能操作三维了，改成结构体即可。
 AC code:
 
#include
using namespace std;

const int N = 35;
char a[N][N][N];
int l,r,c;
int cnt;
typedef struct point
{
    int x,y,z;
}point;
int dx[6] = {1,-1,0,0,0,0};
int dy[6] = {0,0,1,-1,0,0};
int dz[6] = {0,0,0,0,1,-1};
point q[N*N*N];
bool st[N][N][N];
int dist[N][N][N];
void bfs(int sx,int sy,int sz)
{
    dist[sx][sy][sz] = 0;
    st[sx][sy][sz] = true;
    int hh = 0,tt = -1;
    q[++tt] = {sx,sy,sz};
    while(hh<=tt)
    {
        auto t = q[hh++];
        for(int i = 0;i<6;i++)
        {
            int nx = dx[i]+t.x,ny = dy[i]+t.y,nz = dz[i]+t.z;
            if(st[nx][ny][nz]) continue;
            if(nx<0||ny<0||nz<0||nx>=l||ny>=r||nz>=c) continue;
            if(a[nx][ny][nz]=='#') continue;
            st[nx][ny][nz] = true;
            dist[nx][ny][nz] = dist[t.x][t.y][t.z]+1;
            q[++tt] = {nx,ny,nz};
        }
    }
}
int main()
{
    cin>>l>>r>>c;
    int sx,sy,sz,ex,ey,ez;
    for(int i = 0;i>a[i][j][k];
                if(a[i][j][k]=='S')
                {
                    sx = i,sy = j,sz = k;
                }
                if(a[i][j][k]=='E')
                {
                    ex = i,ey = j,ez = k;
                }
            }
        }
    }
    bfs(sx,sy,sz);
    if(dist[ex][ey][ez])
        printf("Escaped in %d minute(s).",dist[ex][ey][ez]);
    else
        printf("Trapped!");
}
 
题目六：P1464 
P1464
 记忆化搜索，要注意dfs时的顺序，还要注意避免访问到非法空间
 AC code:
 
#include 
#include 
#include 
using namespace std;

typedef long long ll;
ll a,b,c;
const int N = 25;
int f[N][N][N];

ll dfs(ll a,ll b,ll c)
{
    if(a<=0||b<=0||c<=0) return 1;
    if(a>20||b>20||c>20) return dfs(20,20,20);
    if(f[a][b][c]) return f[a][b][c];
    if(a>a>>b>>c&&(a!=-1||b!=-1||c!=-1))
    {
        printf("w(%lld, %lld, %lld) = %lldn",a,b,c,dfs(a,b,c));
    }
    return 0;
}
 
难度分割线~ 
题目七：P1019 单词接龙 
P1019
 感觉这个题挺难的，去听了y总讲解然后写了一下。
 
#include
using namespace std;

const int N = 25;
int g[N][N];//g[i][j]表示第i个字符串和第j个字
//符串能够连成的字符串的长度
string word[N];
int used[N];//每个单词使用的次数
int ans,n;

void dfs(string s,int u)
{
    ans = max((int)s.size(),ans);
    used[u]++;
    for(int i = 0;i>n;
    for(int i = 0;i>word[i];
    char start;
    cin>>start;
    for(int i = 0;i