Guest User

Untitled

a guest
Nov 16th, 2018
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.21 KB | None | 0 0
  1. #include<vector>
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<cstdio>
  5. #include<cstring>
  6. using namespace std;
  7. int col[500][500];
  8. char T[500][500];
  9. bool log;
  10. bool vis[500][500];
  11. int cont=0;
  12. vector<int>v;
  13. int clo;
  14. bool f(int posi,int posj){
  15. if(T[posi+1][posj]=='X'&&vis[posi+1][posj])return false;
  16. if(T[posi-1][posj]=='X'&&vis[posi-1][posj])return false;
  17. if(T[posi][posj+1]=='X'&&vis[posi][posj+1])return false;
  18. if(T[posi][posj-1]=='X'&&vis[posi][posj-1])return false;
  19. return true;
  20. }
  21.  
  22. void dfs2(int posi,int posj){
  23. int cont=0;
  24. if(vis[posi][posj])return;
  25. vis[posi][posj]=true;
  26. if(T[posi+1][posj]=='X')dfs2(posi+1,posj);
  27. if(T[posi-1][posj]=='X')dfs2(posi-1,posj);
  28. if(T[posi][posj+1]=='X')dfs2(posi,posj+1);
  29. if(T[posi][posj-1]=='X')dfs2(posi,posj-1);
  30.  
  31.  
  32. }
  33. void dfs(int posi,int posj,char l){
  34. col[posi][posj]=clo;
  35. if(vis[posi][posj])return;
  36. vis[posi][posj]=true;
  37.  
  38. if(T[posi+1][posj]=='*'||T[posi+1][posj]=='X')dfs(posi+1,posj,T[posi][posj]);
  39. if(T[posi-1][posj]=='*'||T[posi-1][posj]=='X')dfs(posi-1,posj,T[posi][posj]);
  40. if(T[posi][posj+1]=='*'||T[posi][posj+1]=='X')dfs(posi,posj+1,T[posi][posj]);
  41. if(T[posi][posj-1]=='*'||T[posi][posj-1]=='X')dfs(posi,posj-1,T[posi][posj]);
  42.  
  43. // if(T[posi+1][posj]=='X'&&!vis[posi+1][posj])if(l=='*'&&f(posi+1,posj))cont++,dfs(posi+1,posj,T[posi][posj]);
  44. // if(T[posi-1][posj]=='X'&&!vis[posi-1][posj])if(l=='*'&&f(posi-1,posj))cont++,dfs(posi-1,posj,T[posi][posj]);
  45. // if(T[posi][posj+1]=='X'&&!vis[posi][posj+1])if(l=='*'&&f(posi,posj+1))cont++,dfs(posi,posj+1,T[posi][posj]);
  46. // if(T[posi][posj-1]=='X'&&!vis[posi][posj-1])if(l=='*'&&f(posi,posj-1))cont++,dfs(posi,posj-1,T[posi][posj]);
  47. }
  48. int k=0;
  49.  
  50. int main(){
  51. while(1){
  52. int a,b;
  53. k++;
  54. memset(vis,false,sizeof(vis));
  55. memset(T,'A',sizeof(T));
  56. scanf("%d%d",&b,&a);
  57. v.clear();
  58. if(a==0&&b==0)break;
  59. for(int i=1;i<=a;i++){
  60. for(int j=1;j<=b;j++){
  61. cin>>T[i][j];
  62. }
  63. }
  64. clo=1;
  65. for(int i=1;i<=a;i++){
  66. for(int j=1;j<=b;j++){
  67. if(vis[i][j])continue;
  68. if((T[i][j]=='*'||T[i][j]=='X')&&!vis[i][j]){
  69. // cout<<i<<" "<<j<<endl;
  70. cont=0;
  71. dfs(i,j,T[i][j]);
  72. clo++;
  73. if(cont!=0)v.push_back(cont);
  74. }
  75. }
  76. }
  77.  
  78. memset(vis,false,sizeof(vis));
  79. for(int i=1;i<=clo;i++){
  80. cont=0;
  81. for(int j=1;j<=a;j++){
  82. for(int r=1;r<=b;r++){
  83. if((T[j][r]=='X')&&!vis[j][r]&&i==col[j][r]){
  84. cont++;
  85. dfs2(j,r);
  86.  
  87. }
  88. }
  89. }
  90. if(cont!=0)v.push_back(cont);
  91. }
  92.  
  93.  
  94. sort(v.begin(),v.end());
  95. printf("Throw %d\n",k);
  96. for(int i=0;i<v.size();i++){
  97. if(i!=v.size()-1)printf("%d ",v[i]);
  98. else printf("%d\n",v[i]);
  99. }
  100. cout<<endl;
  101.  
  102. }
  103. }
Add Comment
Please, Sign In to add comment