70分WA求助
查看原帖
70分WA求助
206023
wzy050703楼主2024/10/18 23:38

萌新写的DFS,WA了#5#9#10,反馈答案大了
怎么回事啊(哭)

#include <stdio.h>
#define isin(x, y) (0 <= x && x < n && 0 <= y && y < n)
/*
    0
3   x   1
    2
*/
int fmove_x[4], fmove_y[4];
void fmoveinit()
{
    fmove_x[0] = -1, fmove_y[0] = 0;
    fmove_x[1] = 0, fmove_y[1] = 1;
    fmove_x[2] = 1, fmove_y[2] = 0;
    fmove_x[3] = 0, fmove_y[3] = -1;
}

int n, ans = 0;
int bookn[100][100];
void DFS(int x, int y, int len)
{
    ans = (ans < len) ? len : ans;
    for (int i = 0; i < 4; i++) // 方向控制
    {
        int nx = x, ny = y;
        nx += fmove_x[i];
        ny += fmove_y[i];
        for (int j = 1; isin(nx, ny); j++) // 距离控制
        {
            if (bookn[nx][ny] != 1)
            {
                if (bookn[nx][ny] == 0 && j > 1)
                {
                    bookn[nx][ny] = -1;
                    DFS(nx, ny, len + j);
                    bookn[x][y] = 0;
                }
                break;
            }
            nx += fmove_x[i];
            ny += fmove_y[i];
        }
    }
    return;
}
int main()
{
    fmoveinit();
    int bx, by;
    scanf("%d%d%d", &n, &bx, &by);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &bookn[i][j]);
        }
    }
    bookn[bx - 1][by - 1] = -1;
    DFS(bx - 1, by - 1, 0);
    printf("%d", ans);
    return 0;
}
2024/10/18 23:38
加载中...