点击刷新
题目链接：https://www.luogu.org/problemnew/show/P1141
做这到题有2点需要注意：
1.发现每个连通的点他们的答案都是一样的！这个很重要，不然后面没法做。
2.接下来就是找连通块了。
题目相当于求连通块，这个比较简单，但加上了m次询问后就是难点所在，很容易超时。所以必须结合1规律做了，他们答案都是一样的！
一定要注意：使用2和3时，关键注意memset(vis,0,sizeof(vis))都不用了，否则还超时（搜索到底什么时候 回溯更新 搞清楚！）
如果搜索有问题，那怎么写都超时！
1.T3，原始，每次询问都搜一遍，70分
1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include <iomanip> 5 #include <cstdio> 6 #include <cstring> 7 #include <cmath> 8 using namespace std; 9 typedef long long ll; 10 typedef unsigned long long ull; 11 const int maxn=1005; 12 char maze[maxn][maxn]; 13 int vis[maxn][maxn]; 14 int n,m; 15 int sx,sy; 16 int ans; 17 18 void so(int x,int y) 19 { 20 //右 21 if(y+1<=n && maze[x][y+1]!=maze[x][y] && vis[x][y+1]==0) { ans++; vis[x][y+1]=1; so(x,y+1); } 22 //下 23 if(x+1<=n && maze[x+1][y]!=maze[x][y] && vis[x+1][y]==0) { ans++; vis[x+1][y]=1; so(x+1,y); } 24 //上 25 if(x-1>=1 && maze[x-1][y]!=maze[x][y] && vis[x-1][y]==0) { ans++; vis[x-1][y]=1; so(x-1,y); } 26 //左 27 if(y-1>=1 && maze[x][y-1]!=maze[x][y] && vis[x][y-1]==0) { ans++; vis[x][y-1]=1; so(x,y-1); } 28 } 29 30 int main() 31 { 32 ios::sync_with_stdio(false); cin.tie(0); 33 34 cin>>n>>m; 35 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>maze[i][j]; 36 37 while(m--) 38 { 39 cin>>sx>>sy; 40 41 memset(vis,0,sizeof(vis)); 42 ans=1; 43 vis[sx][sy]=1; 44 so(sx,sy); 45 46 cout<<ans<<endl; 47 } 48 49 return 0; 50 }
2.将每次找到的联通块都赋予答案，下次就不用再搜了直接输入（本质：最后遍历一遍联通块赋值，相当于记忆化保存），100分
1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include <iomanip> 5 #include <cstdio> 6 #include <cstring> 7 #include <cmath> 8 using namespace std; 9 typedef long long ll; 10 typedef unsigned long long ull; 11 const int maxn=1005; 12 char maze[maxn][maxn]; 13 int vis[maxn][maxn]; 14 int Ans[maxn][maxn]; 15 int n,m; 16 int sx,sy; 17 int ans,anscnt; 18 int p=0,lastp=0; 19 struct px 20 { 21 int x; 22 int y; 23 }T[maxn*maxn+5]; 24 25 void so(int x,int y) 26 { 27 //右 28 if(y+1<=n && maze[x][y+1]!=maze[x][y] && vis[x][y+1]==0) { ans++; vis[x][y+1]=1; T[++p].x=x; T[p].y=y+1; so(x,y+1); } 29 //下 30 if(x+1<=n && maze[x+1][y]!=maze[x][y] && vis[x+1][y]==0) { ans++; vis[x+1][y]=1; T[++p].x=x+1; T[p].y=y; so(x+1,y); } 31 //上 32 if(x-1>=1 && maze[x-1][y]!=maze[x][y] && vis[x-1][y]==0) { ans++; vis[x-1][y]=1; T[++p].x=x-1; T[p].y=y; so(x-1,y); } 33 //左 34 if(y-1>=1 && maze[x][y-1]!=maze[x][y] && vis[x][y-1]==0) { ans++; vis[x][y-1]=1; T[++p].x=x; T[p].y=y-1; so(x,y-1); } 35 } 36 37 int main() 38 { 39 ios::sync_with_stdio(false); cin.tie(0); 40 41 cin>>n>>m; 42 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>maze[i][j]; 43 44 while(m--) 45 { 46 cin>>sx>>sy; 47 48 if(Ans[sx][sy]==0 && anscnt<n*n) 49 { 50 //memset(vis,0,sizeof(vis)); 51 ans=1; 52 vis[sx][sy]=1; 53 so(sx,sy); 54 55 T[++p].x=sx; T[p].y=sy; 56 for(int i=lastp+1;i<=p;i++) 57 { 58 int x=T[i].x,y=T[i].y; 59 Ans[x][y]=ans; 60 anscnt++; 61 } 62 lastp=p; 63 64 cout<<ans<<endl; 65 } 66 else cout<<Ans[sx][sy]<<endl; 67 } 68 69 return 0; 70 }
3.找出父结点代替（本质：集合问题并查集，找出一个代表即可），100分
1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include <iomanip> 5 #include <cstdio> 6 #include <cstring> 7 #include <cmath> 8 using namespace std; 9 typedef long long ll; 10 typedef unsigned long long ull; 11 const int maxn=1005; 12 char maze[maxn][maxn]; 13 int vis[maxn][maxn]; 14 int fax[maxn][maxn],fay[maxn][maxn]; 15 int Ans[maxn][maxn]; 16 int n,m; 17 int sx,sy; 18 int ans; 19 20 void so(int x,int y) 21 { 22 //右 23 if(y+1<=n && maze[x][y+1]!=maze[x][y] && vis[x][y+1]==0) { ans++; vis[x][y+1]=1; fax[x][y+1]=sx; fay[x][y+1]=sy; so(x,y+1); } 24 //下 25 if(x+1<=n && maze[x+1][y]!=maze[x][y] && vis[x+1][y]==0) { ans++; vis[x+1][y]=1; fax[x+1][y]=sx; fay[x+1][y]=sy; so(x+1,y); } 26 //上 27 if(x-1>=1 && maze[x-1][y]!=maze[x][y] && vis[x-1][y]==0) { ans++; vis[x-1][y]=1; fax[x-1][y]=sx; fay[x-1][y]=sy; so(x-1,y); } 28 //左 29 if(y-1>=1 && maze[x][y-1]!=maze[x][y] && vis[x][y-1]==0) { ans++; vis[x][y-1]=1; fax[x][y-1]=sx; fay[x][y-1]=sy; so(x,y-1); } 30 } 31 32 int main() 33 { 34 ios::sync_with_stdio(false); cin.tie(0); 35 36 for(int i=0;i<=maxn-1;i++) for(int j=0;j<=maxn-1;j++) Ans[i][j]=-1; 37 38 cin>>n>>m; 39 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { cin>>maze[i][j]; } 40 41 while(m--) 42 { 43 cin>>sx>>sy; 44 45 if(Ans[fax[sx][sy]][fay[sx][sy]]==-1) 46 { 47 fax[sx][sy]=sx; 48 fay[sx][sy]=sy; 49 //memset(vis,0,sizeof(vis)); 50 ans=1; 51 vis[sx][sy]=1; 52 so(sx,sy); 53 54 Ans[sx][sy]=ans; 55 cout<<Ans[sx][sy]<<endl; 56 } 57 else cout<<Ans[fax[sx][sy]][fay[sx][sy]]<<endl; 58 } 59 60 return 0; 61 }
4.紫书上找连通块最好方法：直接给每个相通的所有连通块一个编号根结点（很nice的方法，并查集集合祖先结点思想！）
1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include <iomanip> 5 #include <cstdio> 6 #include <cstring> 7 #include <cmath> 8 using namespace std; 9 typedef long long ll; 10 typedef unsigned long long ull; 11 const int maxn=1005; 12 char maze[maxn][maxn]; 13 int vis[maxn][maxn]; 14 int Ans[maxn*maxn]; 15 int n,m; 16 int sx,sy; 17 int ans; 18 int cnt;//直接给每个相通的所有连通块一个编号根结点（很nice的方法，并查集集合祖先结点思想！） 19 20 void so(int x,int y,int t) 21 { 22 //右 23 if(y+1<=n && maze[x][y+1]!=maze[x][y] && vis[x][y+1]==0) { ans++; vis[x][y+1]=cnt; so(x,y+1,t); } 24 //下 25 if(x+1<=n && maze[x+1][y]!=maze[x][y] && vis[x+1][y]==0) { ans++; vis[x+1][y]=cnt; so(x+1,y,t); } 26 //上 27 if(x-1>=1 && maze[x-1][y]!=maze[x][y] && vis[x-1][y]==0) { ans++; vis[x-1][y]=cnt; so(x-1,y,t); } 28 //左 29 if(y-1>=1 && maze[x][y-1]!=maze[x][y] && vis[x][y-1]==0) { ans++; vis[x][y-1]=cnt; so(x,y-1,t); } 30 } 31 32 int main() 33 { 34 ios::sync_with_stdio(false); cin.tie(0); 35 36 cin>>n>>m; 37 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>maze[i][j]; 38 39 while(m--) 40 { 41 cin>>sx>>sy; 42 43 //memset(vis,0,sizeof(vis)); 44 int idx=vis[sx][sy]; 45 if(idx==0) 46 { 47 ans=1; 48 vis[sx][sy]=++cnt; 49 so(sx,sy,cnt); 50 51 Ans[cnt]=ans; 52 cout<<Ans[cnt]<<endl; 53 } 54 else cout<<Ans[idx]<<endl; 55 } 56 57 return 0; 58 }
完。
© 著作权归作者所有
举报
发表评论
0/200
