• Source
    1. #include <iostream>
    2. #include <stdio.h>
    3. #include <fstream>
    4. using namespace std;
    5. const int Nmax=1010;
    6. const int d[9]={0,-1,-1,-1, 1,1,1, 0,0};
    7. const int c[9]={0,-1, 0, 1,-1,0,1,-1,1};
    8. int n,m,rest=0;
    9. int a[Nmax][Nmax],b[Nmax][Nmax];
    10. void get_data()
    11. {
    12. int i,j;
    13. cin>>n>>m;
    14. for(i=1;i<=n;i++)
    15. for(j=1; j<=m;j++) cin>>a[i][j];
    16. for(int u=1;u<=n;u++)
    17. for(int v=1;v<=m;v++) b[u][v]=1;
    18. }
    19. void DFS1(int x,int y,int s)
    20. {
    21.  
    22. for(int i=1;i<=8;i++)
    23. {
    24. int u=x+d[i];
    25. int v=y+c[i];
    26. if(0<u && u<=n && 0<v && v<=m &&
    27. b[u][v] && a[u][v]<=a[x][y] && a[u][v]<s)
    28. {
    29. b[u][v]=0;
    30. DFS1(u,v,s);
    31. }
    32. }
    33. }
    34. //============
    35. void DFS2(int x,int y)
    36. {
    37. for(int i=1;i<=8;i++)
    38. {
    39. int u=x+d[i];
    40. int v=y+c[i];
    41. if(0<u && u<=n && 0<v && v<=m && b[u][v])
    42. {
    43. b[u][v]=0;
    44. DFS2(u,v);
    45. }
    46. }
    47. }
    48. //=================
    49. void output()
    50. {
    51. for(int u=1;u<=n;u++)
    52. for(int v=1;v<=m;v++)
    53. if(a[u][v]!=-1) DFS1(u,v,a[u][v]);
    54. for(int u=1;u<=n;u++)
    55. for(int v=1;v<=m;v++)
    56. if(b[u][v])
    57. {
    58. DFS2(u,v);
    59. rest++;
    60. }
    61. cout<<rest<<endl;
    62.  
    63. }
    64. int main()
    65. {
    66. get_data();
    67. output();
    68.  
    69. }
    70.