Problem C: Towards Zero

The Problem

Have you ever heard of this game? The player jumps in a special game board under certain rules, so that the numbers he jumps on, after being linked up by plus or minus signs, get closest to zero.

The game board looks like the one shown in Figure 1.1. Its size is determined by the number of squares in the middle row N. (Figure 1.1 is an example where N = 4.)The player starts at the bottom-most square, then jumps in any of the directions shown in Figure 1.2. The game ends when the player reaches the topmost square. During the game, the player cannot jump out of the game board.Finally we write down the 2N-1 numbers in order, then insert plus or minus signs between each pair of adjoining numbers such that the result is closest to zero.

Let us look at the game board in Figure 1.1 as a example. We should get: 7+8+(-5)+(-2)-5-1-2=0, 7+10+(-7)-6+(-3)-3+2=0, 7+10+(-5)-10-5+1+2=0, or 7+10+(-5)+(-2)-5-3-2=0.

The Input

The first line of input contains N (1 ≤ N ≤ 30). The following 2N-1 lines give the numbers in the squares in the game board. The j-th number in the (i+1)-th line corresponds to the j-th number in the i-th row of the game board. (The numbers are all ≥ -50 and ≤ 50.)

Input contains multiple test cases, and it ends with a case where N = 0.

The Output

For each case, your output should print the absolute value of the result you get for each game board.

Sample Input

423 1-3 5 76 10 -2 20-7 -5 -810 87 0

Sample Output

0

---

由下而上把所有不重複的數字慢慢拓展, 採用 C++ 的 map

//C++ 2.000
#include <stdio.h>
#include <stdlib.h>
#include <map>
using namespace std;

int main() {
    map<int, int> record[60][30];
    int n, i, j, A[60][30];
    while(scanf("%d", &n) == 1 && n) {
        for(i = 0; i < 2*n-1; i++) {
            for(j = 0; j < n-abs(n-i-1); j++) {
                scanf("%d", &A[i][j]);
                if(i != 2*n-2)
                    A[i][j] = abs(A[i][j]);
                record[i][j].clear();
            }
        }
        record[2*n-2][0][A[2*n-2][0]] = 1;
        for(i = 2*n-2; i >= n; i--) {
            for(j = 0; j < n-abs(n-i-1); j++) {
                for(map<int, int>::iterator k = record[i][j].begin(); k != record[i][j].end(); k++) {
                    int v = k->first;
                    record[i-1][j][abs(v+A[i-1][j])] = 1;
                    record[i-1][j][abs(v-A[i-1][j])] = 1;
                    record[i-1][j+1][abs(v+A[i-1][j+1])] = 1;
                    record[i-1][j+1][abs(v-A[i-1][j+1])] = 1;
                }
            }
        }
        for(i = n-1; i >= 1; i--) {
            for(j = 0; j < n-abs(n-i-1); j++) {
                for(map<int, int>::iterator k = record[i][j].begin(); k != record[i][j].end(); k++) {
                    int v = k->first;
                    record[i-1][j][abs(v+A[i-1][j])] = 1;
                    record[i-1][j][abs(v-A[i-1][j])] = 1;
                    if(j) {
                        record[i-1][j-1][abs(v+A[i-1][j-1])] = 1;
                        record[i-1][j-1][abs(v-A[i-1][j-1])] = 1;
                    }
                }
            }
        }
        int min = 0xfffffff;
        for(map<int, int>::iterator i = record[0][0].begin(); i != record[0][0].end(); i++)
            if(abs(i->first) < min)
                min = abs(i->first);
        printf("%d\n", min);
    }
    return 0;
}