DFS + 剪枝

数据加强感觉过不了？

C++ 代码

#include <iostream>
#include <map>
#include <vector>
using namespace std;
const int N = 110;
int map_[N][N];
bool state[N][N][800];
int dx[2] = {-1,-1};//左上右上
int dy[2] = {-1, 1};
int Max_score = -99999999;
int temp_score = 0;
string temp_path;
string Max_path;
int Max_position;
int n, m, k;
void dfs(int x,int y,int region)
{

    if(temp_path.size() == n - 1)
    {
        if(temp_score % (k + 1) != 0) return;
        else
        {
            if (temp_score > Max_score) 
            {
                Max_score = temp_score;
                Max_path = temp_path;
                Max_position = region;  // 更新最大积分时的起始列
            }
            return;
        }
    }
    // auto it = isUsed.find({x,y});
    // if( it != isUsed.end()) return;
    // else isUsed.insert({{x,y},temp_score % (k + 1)});
    if (state[x][y][temp_score]) return;
    state[x][y][temp_score] = true;
    for(int i = 0 ; i < 2 ; i ++)
    {
        int temp_x = x + dx[i];
        int temp_y = y + dy[i];
        if(temp_y < 0 || temp_x < 0 || temp_x >= n || temp_y >= m) continue;
        temp_score += map_[temp_x][temp_y];
        if(i == 0) temp_path += 'L';
        else temp_path += 'R';
        dfs(temp_x,temp_y,region);

        temp_path.pop_back();
        temp_score -= map_[temp_x][temp_y];
    }

}

int main()
{
    cin >> n >> m >> k;
    for(int i = 0; i < n ; i ++)
    {
        string S;
        cin >> S;
        for(int j = 0 ; j < S.size() ; j ++)
        {
            int temp = S[j] - '0';
            map_[i][j] = temp;
        }
    }
    for(int i = 0; i < m ; i ++)
    {
        temp_score = map_[n - 1][i];
        temp_path.clear();
        dfs(n - 1,i,i);
    }
    if(Max_score < 0) cout << -1;
    else
    {
        cout << Max_score << endl;
        cout << Max_position + 1 << endl;
        cout << Max_path << endl;
    }
    return 0;
}