Code666 (代码贴、代码片段)

[C] 矩形嵌套问题 →→→→→进入此内容的聊天室

来自 , 2019-05-14, 写在 C, 查看 97 次.
URL http://www.code666.cn/view/cc099134
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define MAXNUM 100//矩形的最大个数
  5. struct Rect
  6. {
  7.     int x;
  8.     int y;
  9. };
  10.  
  11. int n;//矩形个数
  12. struct Rect rect[MAXNUM];
  13. int G[MAXNUM][MAXNUM];//邻接有向图
  14. int d[MAXNUM];//过程数组
  15.  
  16. int dp(int i,int G[MAXNUM][MAXNUM]);
  17.  
  18. int main()
  19. {
  20.     int i,j,z;
  21.     printf("输入矩形个数n(1-100):\n");
  22.     scanf("%d",&n);
  23.     printf("输入矩形的长和宽：\n");
  24.     for(i=1; i<=n; i++)
  25.     {
  26.         scanf("%d",&rect[i].x);
  27.         scanf("%d",&rect[i].y);
  28.     }
  29.     for(i=1; i<=n; i++)
  30.         for(j=1; j<=n; j++)
  31.         {
  32.             if(rect[i].x<rect[j].x&&rect[i].y<rect[j].y)
  33.                 G[i][j]=1;
  34.         }
  35.     printf("输入要开始的矩形z：\n");
  36.     scanf("%d",&z);
  37.     //printf("%d-",z);
  38.     int temp = dp(z,G);
  39.     printf("最大可嵌套个数：%d\n",temp);
  40.     return 0;
  41. }
  42.  
  43. int dp(int i,int G[MAXNUM][MAXNUM])
  44. {
  45.     int j;
  46.     if(d[i]>0)
  47.         return d[i];
  48.     d[i]=1;
  49.     for(j=1; j<=n; j++)
  50.         if(G[i][j])
  51.             if(dp(j,G)+1>d[i])
  52.             {
  53.                 d[i]=dp(j,G)+1;
  54.             }
  55.     return d[i];
  56. }
  57.  

回复 "矩形嵌套问题"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666