小胖办证

问题描述 【描述 Description 】 xuzhenyi要办个签证。办证处是一座M层的大楼，1<=M<=100。 每层楼都有N个办公室，编号为1..N(1<=N<=500)。每个办公室有一个签证员。 签证需要让第M层的某个签证员盖章才有效。 每个签证员都要满足下面三个条件之一才会给xuzhenyi盖章： 1. 这个签证员在1楼 2. xuzhenyi的签证已经给这个签证员的正楼下（房间号相同）的签证员盖过章了。 3. xuzhenyi的签证已经给这个签证员的相邻房间（房间号相差1，楼层相同）的签证员盖过章了。 每个签证员盖章都要收取一定费用，这个费用不超过1000000000。 找出费用最小的盖章路线，使签证生效 【输入格式 Input Format 】 第1行两个整数M和N。 接下来M行每行N个整数，第i行第j个数表示第i层的第j个签证员收取的费用。 【输出格式 Output Format】 按顺序打出你经过的房间的编号，每行一个数。 如果有多条费用最小的路线，输出任意一条。 【样例输入 Sample Input 】 3 4 10 10 1 10 2 2 2 10 1 10 10 10 【样例输出 Sample Output】 3 3 2 1 1 【算法分析】 DP顺序：从下到上，再从左到右，再从右到左 【代码】

#include 
#include 
#define M 101
#define N 501
int a[M][N], x[M][N], y[M][N], f[M][N];

void print(int xx, int yy)
{
       if (xx < 1 || yy < 1)
              return ;
       print(x[xx][yy], y[xx][yy]);
       printf("%d\n", yy);
}

int main()
{

       int m, n, i, j, min, flag;
       scanf("%d%d", &m, &n);

       for (i = 1; i <= m; i++)
       {
              for (j = 1; j <= n; j++)
                     scanf("%d", &a[i][j]);
       }

       memset(x, 0, sizeof(x));
       memset(y, 0, sizeof(y));
       memset(f, 0, sizeof(f));

       for (j = 1; j <= n; j++)
       {
              f[1][j] = a[1][j];
       }

       for (i = 2; i <= m ; i++)
       {
              for (j = 1; j <= n; j++)
              {
                     f[i][j] = f[i - 1][j] + a[i][j];
                     x[i][j] = i - 1;
                     y[i][j] = j;
              }

              for (j = 2; j <= n; j++)
              {
                     if (a[i][j] + f[i][j - 1] < f[i][j])
                     {
                            f[i][j] = a[i][j] + f[i][j - 1];
                            x[i][j] = i;
                            y[i][j] = j - 1;
                     }     
              }

              for (j = n - 1; j >= 1; j--)
              {
                     if (a[i][j] + f[i][j + 1] < f[i][j])
                     {
                           f[i][j] = a[i][j] + f[i][j + 1];
                            x[i][j] = i;
                            y[i][j] = j + 1;
                     }
              }
       }

       min = 2000000000;

       for (i = 1; i <= n; i++)
       {
              if (f[m][i] < min)
              {
                     min = f[m][i];
                     flag = i;
              }
       }

       print(m, flag);
       return 0;
}