Advertisement
Guest User

Untitled

a guest
Mar 28th, 2020
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.17 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 50;
  4. int vis[N][N];
  5. char graph[N][N];
  6. int n;
  7.  
  8. int ii[8] = {1, 1, 1, 0, 0, -1, -1, -1};
  9. int jj[8] = {-1, 1, 0, -1, 1, 0, 1, -1};
  10.  
  11. bool movimento_valido(int i, int j){
  12. return ((i > 0) && (j > 0) && (i <= n) && (j <= n));
  13. }
  14.  
  15. void DFS(int i, int j){
  16. vis[i][j] = 1;
  17. for(int k = 0; k<8; k++){
  18. int movi = i + ii[k]; //novo movimento em i
  19. int movj = j + jj[k]; //novo movimento em j
  20. if(movimento_valido(movi, movj)){
  21. if(vis[movi][movj] == 0 && graph[movi][movj] == '1') DFS(movi, movj);
  22. }
  23.  
  24. }
  25.  
  26. }
  27.  
  28. int main(){
  29. int ans = 0, cnt = 0;
  30. while(cin >> n){
  31. cnt++;
  32. for(int i = 1; i <= n; i++){
  33. for(int j = 1; j <= n; j++){
  34. cin >> graph[i][j];
  35. }
  36. }
  37. for(int i = 1; i <= n; i++){
  38. for(int j = 1; j <= n; j++){
  39. if(graph[i][j] == '1' && vis[i][j] == 0){
  40. DFS(i, j);
  41. ans++;
  42. }
  43. }
  44. }
  45. cout << "Image number " << cnt << " contains " << ans << " war eagles."<< endl;
  46. ans = 0;
  47. memset(vis, 0, sizeof(vis));
  48. }
  49. return 0;
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement