fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. char str[1010][1010];
  4. int mark[1010][1010];
  5. void bfs(int a,int b, int n, int m)
  6. {
  7. queue<pair<int,int> > q;
  8. q.push(make_pair(a,b));
  9. while(!q.empty())
  10. {
  11. pair<int,int> pp = q.front();
  12. q.pop();
  13. if(mark[pp.first][pp.second])
  14. continue;
  15. mark[pp.first][pp.second] = 1;
  16.  
  17.  
  18. if(str[pp.first][pp.second] == 'S')
  19. {
  20. if(mark[pp.first+1][pp.second]== 0)
  21. q.push(make_pair(pp.first+1,pp.second));
  22. }
  23.  
  24.  
  25.  
  26. if(str[pp.first][pp.second] == 'N')
  27. {
  28. if(mark[pp.first-1][pp.second]== 0)
  29. q.push(make_pair(pp.first-1,pp.second));
  30. }
  31.  
  32.  
  33. if(str[pp.first][pp.second] == 'W')
  34. {
  35. if(mark[pp.first][pp.second-1]== 0)
  36. q.push(make_pair(pp.first,pp.second-1));
  37. }
  38.  
  39.  
  40. if(str[pp.first][pp.second] == 'E')
  41. {
  42. if(mark[pp.first][pp.second+1]== 0)
  43. q.push(make_pair(pp.first,pp.second+1));
  44. }
  45.  
  46.  
  47.  
  48. if(pp.first < n-1 && str[pp.first+1][pp.second] == 'N' && mark[pp.first+1][pp.second] == 0)
  49. {
  50. q.push(make_pair(pp.first+1,pp.second));
  51. }
  52.  
  53. if(pp.first > 0 && str[pp.first-1][pp.second] == 'S' && mark[pp.first-1][pp.second] == 0)
  54. {
  55. q.push(make_pair(pp.first-1,pp.second));
  56. }
  57.  
  58. if(pp.second < m-1 && str[pp.first][pp.second+1] == 'W' && mark[pp.first][pp.second+1] == 0)
  59. {
  60. q.push(make_pair(pp.first,pp.second+1));
  61. }
  62.  
  63. if(pp.second > 0 && str[pp.first][pp.second-1] == 'E' && mark[pp.first][pp.second-1] == 0)
  64. {
  65. q.push(make_pair(pp.first,pp.second-1));
  66. }
  67.  
  68.  
  69.  
  70.  
  71. }
  72. }
  73. int main()
  74. {
  75.     int n,m;
  76.     scanf("%d %d",&n,&m);
  77.     for(int i = 0; i < n;i++)
  78.     {
  79.         scanf("%s",str[i]);
  80.     }
  81.     int ans = 0;
  82.     for(int  i = 0 ; i < n;i++)
  83.     {
  84.         for(int  j = 0 ; j < m;j++)
  85.         {
  86.             if(mark[i][j] == 0)
  87.             {
  88.                 ans++;
  89.                 bfs(i,j,n,m);
  90.             }
  91.         }
  92.     }
  93.     printf("%d\n",ans);
  94. }
  95.  
Time limit exceeded #stdin #stdout 5s 8128KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/F8QNys
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!