问题描述
【描述 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顺序：从下到上，再从左到右，再从右到左 【代码】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | #include <stdio.h> #include <string.h> #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; } |
Pingback引用通告： cell