搜索做题笔记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
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）