70pts 3TLE dfs求正解
查看原帖
70pts 3TLE dfs求正解
583610
DrAlfred楼主2022/9/24 13:18
#include <bits/stdc++.h>
using namespace std;
int n, ans, matrix[101][101];
bool foundAns[101][101][101];
inline bool judgeMatrix(int x, int y, int size) {
    // 判断左斜线
    for (int i = 0; i < size; i++) {
        int lx = x + i, ly = y + i;
        if (matrix[lx][ly] == 0) {
            return false;
        }
    }
    // 右边斜线
    int lx = x + size - 1, ly = y;
    while (lx >= x) {
        if (matrix[lx][ly] == 0) {
            return false;
        }
        --lx;
        ++ly;
    }
    return true;
}
inline void dfs(int begx, int begy ,int size) {
    if (size == 1) {
        return;
    }
    if (foundAns[begx][begy][size]) {
        return;
    }
    foundAns[begx][begy][size] = true;
    if (judgeMatrix(begx, begy, size)) {
        ++ans;
    }
    int nextSize = size - 1;
    for (int nextX = begx; nextX + nextSize - 1 <= n; nextX++) {
        for (int nextY = begy; nextY + nextSize - 1 <= n;nextY++) {
            dfs(nextX, nextY, nextSize);
        }
    }
}
int main(int argc, char const *argv[]) {
    scanf("%d", &n);
    for (int i = 1; i <= n;i++) {
        for (int j = 1; j <= n;j++) {
            scanf("%1d", &matrix[i][j]);
        }
    }
    // puts("scan succeeded");
    dfs(1, 1, n);
    printf("%d\n", ans);
    system("pause");
    return 0;
}

2022/9/24 13:18
加载中...