今天做https://www.luogu.com.cn/problem/P2049

刚开始想到dfs,过了一个测试点，全紫

加个访问数组，防止访问重复的点

因为显而易见答案肯定在0-k

cpp
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_M 100
#define MAX_N 100
#define MAX_K 100

int M, N, K;
int grid[MAX_M][MAX_N];
bool visited[MAX_M][MAX_N][MAX_K];
bool results[MAX_K];

void dfs(int x, int y, int value) {
    if (visited[x][y][value]) return;
    visited[x][y][value] = true;

    if (x == M - 1 && y == N - 1) {
        // 到达右下角，记录结果
        results[value] = true;
        return;
    }

    // 向右走
    if (y + 1 < N) {
        dfs(x, y + 1, (value * grid[x][y + 1]) % K);
    }

    // 向下走
    if (x + 1 < M) {
        dfs(x + 1, y, (value * grid[x + 1][y]) % K);
    }
}

int main() {
    scanf("%d %d %d", &M, &N, &K);
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &grid[i][j]);
        }
    }

    // 从左上角开始DFS
    dfs(0, 0, grid[0][0] % K);

    // 收集结果
    int result_count = 0;
    for (int k = 0; k < K; k++) {
        if (results[k]) {
            result_count++;
        }
    }

    // 输出结果
    printf("%d\n", result_count);
    for (int k = 0; k < K; k++) {
        if (results[k]) {
            printf("%d ", k);
        }
    }
    printf("\n");

    return 0;
}

还有dp解法

cpp
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_M 100
#define MAX_N 100
#define MAX_K 100

int M, N, K;
int grid[MAX_M][MAX_N];
bool dp[MAX_M][MAX_N][MAX_K];

int main() {
    scanf("%d %d %d", &M, &N, &K);
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d", &grid[i][j]);
        }
    }

    // 初始化起点
    dp[0][0][grid[0][0] % K] = true;

    // 动态规划
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            if (i == 0 && j == 0) continue;
            for (int k = 0; k < K; k++) {
                if (i > 0 && dp[i-1][j][k]) {
                    dp[i][j][(k * grid[i][j]) % K] = true;
                }
                if (j > 0 && dp[i][j-1][k]) {
                    dp[i][j][(k * grid[i][j]) % K] = true;
                }
            }
        }
    }

    // 收集结果
    int results[MAX_K];
    int result_count = 0;
    for (int k = 0; k < K; k++) {
        if (dp[M-1][N-1][k]) {
            results[result_count++] = k;
        }
    }

    // 输出结果
    printf("%d\n", result_count);
    for (int i = 0; i < result_count; i++) {
        printf("%d ", results[i]);
    }
    printf("\n");

    return 0;
}