• Source
    1. /**************************************************************
    2.   Problem: 1102
    3.   User: zrts
    4.   Language: C++
    5.   Result: Accepted
    6.   Time:3872 ms
    7.   Memory:19336 kb
    8. ****************************************************************/
    9.  
    10.  
    11. //永远做自己会做的题就永远还是原来的样子
    12. #include<cstdio>
    13. #include<cstring>
    14. //by zrt
    15. //problem:
    16. using namespace std;
    17. int n,n2;
    18. int f[1000005];
    19. bool vis[1000005];
    20. int a[1005][1005];
    21. bool higher[1005][1005];
    22. bool lower[1005][1005];
    23. int get(int x){
    24. return x==f[x]?x:f[x]=get(f[x]);
    25. }
    26. int xk[]={0,1,1};
    27. int yk[]={1,0,1};
    28. int Xk[]={1,1,1,0,0,-1,-1,-1};
    29. int Yk[]={1,0,-1,-1,1,1,0,-1};
    30. int main(){
    31. #ifdef LOCAL
    32. freopen("in.txt","r",stdin);
    33. freopen("out.txt","w",stdout);
    34. #endif
    35. scanf("%d",&n);
    36. n2=n*n;
    37. for(int i=0;i<n;i++){
    38. for(int j=0;j<n;j++){
    39. scanf("%d",&a[i][j]);
    40. }
    41. }
    42. for(int i=0;i<=n2;i++) f[i]=i;
    43. int x,y;
    44. for(int i=0;i<n;i++){
    45. for(int j=0;j<n;j++){
    46. for(int k=0;k<8;k++){
    47. x=i+Xk[k];y=j+Yk[k];
    48. if(x>=0&&y>=0&&x<n&&y<n){
    49. if(a[i][j]==a[x][y]){
    50. f[get(i*n+j)]=get(x*n+y);
    51. }
    52. }
    53. }
    54. }
    55. }
    56. for(int i=0;i<n;i++){
    57. for(int j=0;j<n;j++){
    58. if(i==2&&j==3){
    59. i=2;j=3;
    60. }
    61. for(int k=0;k<8;k++){
    62. x=i+Xk[k];y=j+Yk[k];
    63. if(x>=0&&y>=0&&x<n&&y<n){
    64. if(a[i][j]!=a[x][y]){
    65. if(a[i][j]<a[x][y]){
    66. int p=get(i*n+j);
    67. higher[p/n][p%n]=1;
    68. }else{
    69. int p=get(i*n+j);
    70. lower[p/n][p%n]=1;
    71. }
    72. }
    73. }
    74. }
    75. }
    76. }
    77. int sf=0,sg=0;
    78. for(int i=0;i<n;i++){
    79. for(int j=0;j<n;j++){
    80. int k=get(i*n+j);
    81. if(!vis[k]){
    82. vis[k]=1;
    83. if(!higher[k/n][k%n]){
    84. sf++;
    85. // printf("sf %d %d\n",k/n+1,k%n+1);
    86. }
    87. if(!lower[k/n][k%n]){
    88. sg++;
    89. // printf("sg %d %d\n",k/n+1,k%n+1);
    90. }
    91. }
    92. }
    93. }
    94. printf("%d %d",sf,sg);
    95. return 0;
    96. }