矩形嵌套问题

[c]代码库

#include <stdio.h>
#include <stdlib.h>

#define MAXNUM 100//矩形的最大个数
struct Rect
{
    int x;
    int y;
};

int n;//矩形个数
struct Rect rect[MAXNUM];
int G[MAXNUM][MAXNUM];//邻接有向图
int d[MAXNUM];//过程数组

int dp(int i,int G[MAXNUM][MAXNUM]);

int main()
{
    int i,j,z;
    printf("输入矩形个数n(1-100):\n");
    scanf("%d",&n);
    printf("输入矩形的长和宽：\n");
    for(i=1; i<=n; i++)
    {
        scanf("%d",&rect[i].x);
        scanf("%d",&rect[i].y);
    }
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
        {
            if(rect[i].x<rect[j].x&&rect[i].y<rect[j].y)
                G[i][j]=1;
        }
    printf("输入要开始的矩形z：\n");
    scanf("%d",&z);
    //printf("%d-",z);
    int temp = dp(z,G);
    printf("最大可嵌套个数：%d\n",temp);
    return 0;
}

int dp(int i,int G[MAXNUM][MAXNUM])
{
    int j;
    if(d[i]>0)
        return d[i];
    d[i]=1;
    for(j=1; j<=n; j++)
        if(G[i][j])
            if(dp(j,G)+1>d[i])
            {
                d[i]=dp(j,G)+1;
            }
    return d[i];
}