Paths through the Hourglass

In the hourglass to the right a path is marked. A path always starts at the first row and ends at the last row. Each cell in the path (except the first) should be directly below to the left or right of the cell in the path in the previous row. The value of a path is the sum of the values in each cell in the path.

A path is described with an integer representing the starting point in the first row (the leftmost cell being 0) followed by a direction string containing the letters L and R, telling whether to go to the left or right. For instance, the path to the right is described as 2 RRRLLRRRLR.

Given the values of each cell in an hourglass as well as an integer S, calculate the number of distinct paths with value S. If at least one pathexist, you should also print the path with the lowest starting point. If several such paths exist, select the one which has the lexicographically smallest direction string.

Input

The input contains several cases. Each case starts with a line containing two integers N and S (2≤N≤20, 0≤S<500), the number of cells in the first row of the hourglass and the desired sum. Next follows 2N-1 lines describing each row in the hourglass. Each line contains a space separated list of integers between 0 and 9 inclusive. The first of these lines will contain N integers, then N-1, ..., 2, 1, 2, ..., N-1, N.

The input will terminate with N=S=0. This case should not be processed. There will be less than 30 cases in the input.

Output

For each case, first output the number of distinct paths. If at least one path exist, output on the next line the description of the path mentioned above. If no path exist, output a blank line instead.

Sample Input Output for Sample Input

6 41

6 7 2 3 6 8

1 8 0 7 1

2 6 5 7

3 1 0

7 6

8 8

6 5 3

9 5 9 5

6 4 4 1 3

2 6 9 4 3 8

2 7

3 1

3 5

5 26

2 8 7 2 5

3 6 0 2

1 3 4

2 5

7 2

2 9 3

1 0 4 4

4 8 7 2 3

0 0

2 RRRLLRRRLR

2 RLLRRRLR

/*
题意，从上到下，用给定的步数恰好走到底部。
输出不同的路径数和起点最小时的坐标和路径。

从下往上遍历，为什么？
若从上到下，会发现到达底部的时候是看dp的值是否为0来判断是否有路径到达这里。
很明显这样根本不能知道起点的信息。
所以从下往上遍历，会发现到达顶部的时候也是看dp的值来判断是否有路径到达该点。 
直接找到那个最小坐标的点就是最小起点。

每次从下到上遍历，分为2部分：上层和下层，因为它们结构不一样。

交了将近20次！！！ 
1.
被long long坑了，最后数据比较大，用int会RE. 
N = 22 S = 502 居然还RE.艹 
2.
最大的坑，初始化不对，以为初始化 0-n-1 就行了，其实不是，这个数组是从0-(2*n-2)啊啊啊啊!!
3.
若发现dp2更新后若比s还大，则不更新dp2 
4.
因为n最大为20，所以数组不能开22啊，坑！！！！明明都已经知道了所以N至少得40多啊 S也要1000啊 
*/
#include <iostream>
#include <cstring>
using namespace std;

#define N 50
#define S 1000

long long n, s;
long long f[N][N];
long long dp[N][N][S];    //到达i,j时，已经走k步的时候的不同路径数。 （从下往上） 
long long dp2[N][N][S];    //到达i,j时已经走了的步数 
string dp3[N][N][S], ans;    //到达i,j时，已经走k步的时候记录如何到达底部。 
long long sum, start;

void input()
{
    for (int i = 0, k = n; i < n; ++i, --k)
    {
        for (int j = 0; j < k; ++j)
        {
            cin >> f[i][j];
        }
    }
    
    for (int i = n, k = 2; i < 2*n-1; ++i, ++k)
    {
        for (int j = 0; j < k; ++j)
        {
            cin >> f[i][j];
        }
    }    
}

void init()
{
    ans = "";
    start = sum = 0;
    memset(f,0,sizeof(f));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            for (int k = 0; k < S; ++k)
                dp[i][j][k] = 0, dp2[i][j][k] = -1,dp3[i][j][k] = "";    
                //dp2初始化为-1，不然s=0时在最后判断是否有路的时候，没路那些也符合了 
}

void solve()
{
    //因为要起点的坐标最小，所以我们从下往上推，到达第一层的时候看dp不为0的第一个坐标就是最小坐标 
    //Last row
    for (int j = 0; j < n; ++j)
    {
        dp2[2*n-2][j][f[2*n-2][j]] = f[2*n-2][j];
        
        dp[2*n-2][j][f[2*n-2][j]] = 1;
    }
    //lower
    for (int i = 2*n-3, k = n-1; i >= n-1; --i,--k)
    {
        for (int j = 0; j < k; ++j)
        {
            for (int p = 0; p <= s; ++p)
            {
                //先判断R再判断L，这样当左右都可以走的时候左边的路（dp3） 就会覆盖掉右边的路 
                //用dp判断不用dp2判断，因为有可能起点本来就是0，那么以那个点为起点的路就不存在了 
                if (dp[i+1][j+1][p] != 0 && p+f[i][j] <= s)    //若发现dp2更新后若比s还大，则不更新dp2
                {
                    dp2[i][j][p+f[i][j]] = p+f[i][j];
                    
                    dp[i][j][p+f[i][j]] += dp[i+1][j+1][p];
                    
                    dp3[i][j][p+f[i][j]] = "R" + dp3[i+1][j+1][p];
                }
                if(dp[i+1][j][p] != 0 && p+f[i][j] <= s)
                {
                    dp2[i][j][p+f[i][j]] = p+f[i][j];
                    
                    dp[i][j][p+f[i][j]] += dp[i+1][j][p];
                    
                    dp3[i][j][p+f[i][j]] = "L" + dp3[i+1][j][p];    //若右边可以走，在这里就会覆盖回去 
                }

            }
        }
    }
    //upper
    for (int i = n-2, k = 2; i >= 0; --i,++k)
    {
        for (int j = 0; j < k; ++j)
        {
            for (int p = 0; p <= s; ++p)
            {
                if (dp[i+1][j][p] != 0 && j != k-1 && p+f[i][j] <= s)
                {
                    dp2[i][j][p+f[i][j]] = p+f[i][j];
                    
                    dp[i][j][p+f[i][j]] += dp[i+1][j][p];
                    
                    dp3[i][j][p+f[i][j]] = "R" + dp3[i+1][j][p];
                }
                if (dp[i+1][j-1][p] != 0 && j != 0 && p+f[i][j] <= s)
                {
                    dp2[i][j][p+f[i][j]] = p+f[i][j];
                    
                    dp[i][j][p+f[i][j]] += dp[i+1][j-1][p];
                    
                    dp3[i][j][p+f[i][j]] = "L" + dp3[i+1][j-1][p];
                }
            }
        }
    }

    
    for (int j = n-1; j >= 0; --j)
    {
        if (dp2[0][j][s] == s)
        {
            sum += dp[0][j][s];
            
            start = j;
        }
    }
    
    cout << sum << endl;
    
    if (sum != 0)
        cout << start << ' ' << dp3[0][start][s];
    cout << endl;
}

int main()
{    
    while (cin >> n >> s, n||s)
    {
        init();
        
        input();
        
        solve();
    }
}

View Code