-
搜索专题练习
隔了N年之后，来写写搜索专题，
然后第一题我就卡住了
P1443 马的遍历
给一个n*m的棋盘(x,y)上有一个马，问马能到棋盘上任意一点最少要走几步。
看来我对dfs和bfs还是有误区，这题我一看就想着用dfs来做，但是我又不知道dfs时间复杂度是多少，就打算不管了，先写一个再说，然后就写了一个这样的
int dfs(int x,int y) { if(x<1||x>n||y<1||y>m)return; if(ans[x][y]!=-1)return ans[x][y]; for(int i=0;i<8;i++){ int X=x+dx[i],Y=y+dy[i]; if(X<1||X>n||Y<1||Y>m)continue; // ans[X][Y]=dfs(x,y)+1; } return ans[x][y]; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
可以看到上边我这个"dfs"他没写递归，因为啥呢，因为我不知道怎么写了，如果给dfs一个int最为返回值的话，就表示从起点到当前这个点(x,y)的最小距离,
写完这句话之后我好像突然知道我哪里错了，就马上去改，然后有了下边这个代码int X,Y; int dfs(int x,int y) { if(ans[x][y]!=-1&&(x!=X)&&(y!=Y))return ans[x][y]; for(int i=0;i<8;i++){ int X=x+dx[i],Y=y+dy[i]; if(X<1||X>n||Y<1||Y>m)continue; // ans[X][Y]=dfs(x,y)+1; } return ans[x][y]; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
然后发现这段代码是死循环，我没法结束它，怎么改呢，如果我们发现dfs不好写的话，我们可以试着多给dfs一些参数。
然后我终于过样例了int cnt=0; void dfs(int x,int y,int res) { cnt++; cout<<x<<" "<<y<<endl; // if(ans[x][y]!=0x3f3f3f3f)return ; ans[x][y]=min(ans[x][y],res); if(res>n*m-1)return ; if(x<1||x>n||y<1||y>m)return ; for(int i=0;i<8;i++){ int X=x+dx[i],Y=y+dy[i]; if(X<1||X>n||Y<1||Y>m)continue; dfs(X,Y,res+1); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
长这个熊样，中间想着应该可以记忆化吧，结果是错了，输出想了一下确实不能记忆化，因为你从第一个方向向后扩展得到的答案不是最优解 ，样例是3 3 1 1 ，cnt竟然达到了1023，我丢，吓人啊。
~~然后我交了一发，10分，nice ~~
然后我就去题解了找dfs的代码，
这时才发现这题正解是bfs，我丢，dfs站不起来了？找了一份思路类似但是实现顺序不同的代码交了上去，80分，
what‘s up?void dfs(int x,int y,int res) { ans[x][y]=res; // cout<- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
那么大家有没有想过：为什么会TLE呢？
我们都知道dfs是一条路搜到黑，所以不可以保证最开始搜到的就是最近点。也就是说，我们在遍历的过程中，结果是在不断更新的。
那么就是说我们把马所有可能走的路径全都搜索了一遍，有很多搜索都是累赘的。
然后我就转向了bfs
void bfs(int x,int y) { mem(ans,-1); queue<PII>que; que.push({x,y}); ans[x][y]=0; while(que.size()) { PII t=que.front(); que.pop(); for(int i=0;i<8;i++){ int X=t.first+dx[i],Y=t.second+dy[i]; if(X<1||X>n||Y<1||Y>m)continue; if(ans[X][Y]!=-1)continue; ans[X][Y]=ans[t.first][t.second]+1; // 写成了 ans[X][Y]=ans[x][y]+1,哎 que.push({X,Y}); } } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
一个小时写了一道被写烂的黄题，离谱哇。
这次再写搜索专题已经是2021.10.14了，记录一下，今天凌晨div3 打到了1100，自己打的出了五道，不过A题竟然被卡了，血亏啊。
P1605 迷宫
刚才竟然被迷宫卡了，就是迷宫有障碍物，给一个起点和终点，问有多少条路径
来看看我写的dfs
一开始没写回溯，wa傻了，写了之后是70，然后我搞不懂dfs是什么意思了，
看代码的话，dfs应该是已经遍历到x，y节点时的状态，所以28~30行就解释的通了。
但是代码有个bug就是，一开始就从sx，sy开始dfs的，但是dfs里边是没有对起点的S数组打标记的，所以需要补一个标记，然后就没然后了。对了，学到了一个方向数组的trick
四方向 int d[]={-1,0,1,0,-1}; 简化之后 for(int i=0;i<4;i++) { int nx=x+d[i],ny=y+d[i+1];//帅啊 } 八方向 int dx[]={-1,-1,0,1,1,1,0,-1} int dy[]={0,1,1,1,0,-1,-1,-1}; 可以写成 int d[]={-1,-1,0,1,1,1,0,-1,-1,-1}; for(int i=0;i<8;i++){ int nx=x+d[i]; int ny=y+d[i+2];//8方向是加2 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
ll n,m,_,k,p; bool st[10][10]; int fx,fy; int dx[]={-1,0,1,0}; int dy[]={0,1,0,-1}; int ans; bool S[10][10]; void dfs(int x,int y) { // cout<- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
单词方阵
又是一道黄体，这次和迷宫不一样，我没被卡，1次编译通过，一次ac，但是我写了一个特长的伪搜索，没有写简单的代码，看了看题解中的代码比我的短很多，这要是cf上的题，我又要gg了。
思路非常简单，就是对于每个字母进行一次匹配, O(n*n*8*6)==O(4.8e5) bool st[110][110]; char mp[110][110]; string s="yizhong"; bool check(int x,int y,int d) { if(d==0){//(x,y)向上能否延申6个单位 if(x-6<1)return false; for(int j=0;j<=6;j++){ if(mp[x-j][y]!=s[j])return false; } return true; } else if(d==1){ if(x-6<1||y+6>n)return false; for(int j=0;j<=6;j++){ if(mp[x-j][y+j]!=s[j])return false; } return true; } else if(d==2){ if(y+6>n)return false; for(int j=0;j<=6;j++){ if(mp[x][y+j]!=s[j])return false; } return true; } else if(d==3){ if(x+6>n||y+6>n)return false; for(int j=0;j<=6;j++){ if(mp[x+j][y+j]!=s[j])return false; } return true; } else if(d==4){ if(x+6>n)return false; for(int j=0;j<=6;j++){ if(mp[x+j][y]!=s[j])return false; } return true; } else if(d==5){ if(x+6>n||y-6<1)return false; for(int j=0;j<=6;j++){ if(mp[x+j][y-j]!=s[j])return false; } return true; } else if(d==6){ if(y-6<1)return false; for(int j=0;j<=6;j++){ if(mp[x][y-j]!=s[j])return false; } return true; } else if(d==7){ if(x-6<1||y-6<1)return false; for(int j=0;j<=6;j++){ if(mp[x-j][y-j]!=s[j])return false; } return true; } } void cover(int x,int y,int d) { /* 01234567 上 右 下 左 */ if(d==0){ for(int j=0;j<=6;j++){ st[x-j][y]=1; } } else if(d==1){ for(int j=0;j<=6;j++){ st[x-j][y+j]=1; } } else if(d==2){ for(int j=0;j<=6;j++){ st[x][y+j]=1; } } else if(d==3){ for(int j=0;j<=6;j++){ st[x+j][y+j]=1; } } else if(d==4){ for(int j=0;j<=6;j++){ st[x+j][y]=1; } } else if(d==5){ for(int j=0;j<=6;j++){ st[x+j][y-j]=1; } } else if(d==6){ for(int j=0;j<=6;j++){ st[x][y-j]=1; } } else if(d==7){ for(int j=0;j<=6;j++){ st[x-j][y-j]=1; } } } void solve() { cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>mp[i][j]; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { for(int k=0;k<8;k++) { if(check(i,j,k)){ cover(i,j,k); } } } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(!st[i][j])cout<<"*"; else{ cout<<mp[i][j]; } } cout<<endl; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
大佬写的dfs的代码
dfs的思路就是给出每个点向8个点的便宜方向，然后给一个next步数，先是找出了 所有的y在哪里，然后再进行dfs，写的很棒！ #includeusing namespace std; int c[10000][2],d=0,x[9]={0,1,0,1,-1,0,-1,1,-1}; int y[9]={0,0,1,1,0,-1,-1,-1,1}; char a[103][103],b,k[9]=" yizhong"; bool s[102][102]; bool f(int i,int j,int m,int n,int next){ if(next>=8){ s[i][j]=1; return 1; } if(a[i+m][j+n]==k[next]) if(f(i+m,j+n,m,n,next+1)){ s[i][j]=1; return 1; } return 0; } int main(){ int n,i,j,o; cin>>n; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ cin>>b; if(b=='y'){ c[++d][0]=i; c[d][1]=j; } a[i][j]=b; } } while(d){ i=c[d][0]; j=c[d][1]; for(o=1;o<=8;o++){ if(a[i+x[o]][j+y[o]]=='i') if(f(i+x[o],j+y[o],x[o],y[o],3)) s[i][j]=1; } d--; } for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(s[i][j])cout<<a[i][j]; else cout<<"*"; } cout<<endl; } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
P1596 [USACO10OCT]Lake Counting S
哎，真实服气了，dfs判断连通块的个数这种题目都能过卡住我了。
for循环如果某个点是水坑的话，就去dfs这个点，用st数组打标记。char mp[110][110]; bool st[110][110]; int ans; int dx[]={-1,-1,0,1,1,1,0,-1}; int dy[]={0,1,1,1,0,-1,-1,-1}; void dfs(int x,int y) { st[x][y]=1; for(int i=0;i<8;i++) { int nx=x+dx[i]; int ny=y+dy[i]; if(nx<1||nx>n||ny<1||ny>m)continue; if(st[nx][ny])continue; if(mp[nx][ny]=='.')continue; dfs(nx,ny); } } void solve() { cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++){ cin>>mp[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(mp[i][j]=='W'&&(!st[i][j])){ dfs(i,j); ans++; } } } cout<<ans<<endl; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
P1162 填涂颜色
又被橙题给卡了 ，愣是不知道这个-1怎么处理。
只有48分，太丢人了 #include#include #include #include #include #include #include #include #include #include #define pb push_back #define all(x) (x).begin(),(x).end() #define mem(f, x) memset(f,x,sizeof(f)) #define fo(i,a,n) for(int i=(a);i<=(n);++i) #define fo_(i,a,n) for(int i=(a);i<(n);++i) #define debug(x) cout<<#x<<":"<<x<<endl; #define endl '\n' using namespace std; template<typename T> ostream& operator<<(ostream& os,const vector<T>&v){for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){j=0;puts("");}else os<<v[i]<<" ";return os;} template<typename T> ostream& operator<<(ostream& os,const set<T>&v){for(auto c:v)os<<c<<" ";return os;} template<typename T1,typename T2> ostream& operator<<(ostream& os,const map<T1,T2>&v){for(auto c:v)os<<c.first<<" "<<c.second<<endl;return os;} template<typename T>inline void rd(T &a) { char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {if (c == '-')f = -1; c = getchar();} while (isdigit(c)) {x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x; } typedef pair<int,int>PII; typedef pair<long,long>PLL; typedef long long ll; typedef unsigned long long ull; const int N=2e5+10,M=1e9+7; ll n,m,_; int mp[110][110]; bool st[110][110];//判断有没有搜索过, int col[110][110]; int ans; int dx[]={-1,0,1,0}; int dy[]={0,1,0,-1}; int dfs(int x,int y)//判断(x,y)染成什么颜色 { st[x][y]=1; for(int i=0;i<4;i++) { int nx=x+dx[i]; int ny=y+dy[i]; if(nx<1||nx>n||ny<1||ny>m){//闭合圈 //和(x,y)联通的0都不会染色 return -1;//不会在边上的 } if(col[nx][ny]==-1){ cout<<x<<" "<<y<<endl; col[nx][ny]=dfs(nx,ny); return -1; } if(st[nx][ny])continue; if(mp[nx][ny]==1)continue; col[nx][ny]=dfs(nx,ny); } return 2; } void solve() { freopen("P1162_3.in","r",stdin); cin>>n; m=n; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++){ cin>>mp[i][j]; col[i][j]=mp[i][j]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(mp[i][j]==0&&!st[i][j]){ col[i][j]=dfs(i,j); } } } cout<<endl; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cout<<col[i][j]<<" "; } cout<<endl; } cout<<endl; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(col[i][j]==-1) col[i][j]=0; cout<<col[i][j]<<" "; } cout<<endl; } } int main() { solve(); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
扩展边界。 #includeusing namespace std; int a[32][32],b[32][32]; int dx[5]={0,-1,1,0,0}; int dy[5]={0,0,0,-1,1};//第一个表示不动，是充数的，后面的四个分别是上下左右四个方向 int n,i,j; void dfs(int p,int q){ int i; if (p<0||p>n+1||q<0||q>n+1||a[p][q]!=0) return;//如果搜过头或者已经被搜过了或者本来就是墙的就往回 a[p][q]=1;//染色 for (i=1;i<=4;i++) dfs(p+dx[i],q+dy[i]);//向四个方向搜索 } int main(){ cin>>n; for (i=1;i<=n;i++) for (j=1;j<=n;j++){ cin>>b[i][j];//其实不拿两个数组也可以，不过我喜欢啦 if (b[i][j]==0) a[i][j]=0; else a[i][j]=2; } dfs(0,0);//搜索 从0，0开始搜 , 相当于边界都加宽了 , 四面八方的0都可以被搜索到 ，妙 for (i=1;i<=n;i++){ for (j=1;j<=n;j++) if (a[i][j]==0) cout<<2<<' ';//如果染过色以后i，j那个地方还是0，说明没有搜到，就是周围有墙，当然就是被围住了，然后输出2 else cout<<b[i][j]<<' ';//因为被染色了，本来没有被围住的水和墙都染成了1，所以就输出b[i][j] cout<<'\n';//换行 } } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
-
相关阅读:
Java中如何获取File大小,路径,修改时间,是否隐藏文件等属性呢？
-找树根-
EXCEL快速填充空白内容
Pandas数据集的合并与连接merge()方法_Python数据分析与可视化
css3d制作正方体
【JavaScript流程控制-分支】
echarts实现中国地图各省背景根据数值大小变化的方法
FFmpeg入门及编译
Java练习 day1(LeetCode简单题15道）
标题采集软件-免费标题生成器
- 原文地址：https://blog.csdn.net/hacker__man/article/details/125914453
