90pts TLE on test4 求助

遥遥领先 @ 2024-06-28 14:10:56

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n,a[110][110];
char aa[110][110];
int sx,sy,ex,ey,f;
int ans;

const int fx[4] = {-1,0,0,1};
const int fy[4] = {0,-1,1,0};

void dfs(int x,int y,int t,int k)
{
    if (ans <= k) return ;
    if (x == ex && y == ey) {ans = min(ans,k);f = 1;return ;}
    for (int i = 0;i < 4;i++)
    {
        int xx = x + fx[i],yy = y + fy[i];
        if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && a[xx][yy])
        {
            a[xx][yy] = 0;
            int now = 0;
            if (i != t)
                now = 1;
            if (t == -1)
                now = 0;
            dfs(xx,yy,i,k+now);
            a[xx][yy] = 1;
        }
    }
}

void solve()
{
    ans = 2e9;
    scanf("%lld",&n);
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= n;j++)
        {
            cin >> aa[i][j];
            if (aa[i][j] == '.')
                a[i][j] = 1;
            if (aa[i][j] == 'A')
                sx = i,sy = j;
            if (aa[i][j] == 'B')
                ex = i,ey = j,a[i][j] = 1;
        }
    dfs(sx,sy,-1,0);
    if (f) printf("%lld",ans);
    else printf("-1");
}

signed main()
{
    solve();
    printf("\n");
    return 0;
}

by dhlzzsx @ 2024-06-29 08:41:16

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n,a[110][110];
char aa[110][110];
int sx,sy,ex,ey,f;
int ans;
//改方向数组
const int fx[4] = {1,0,-1,0};
const int fy[4] = {0,-1,0,1};

void dfs(int x,int y,int t,int k)
{
    if (ans <= k) return ;
    if (x == ex && y == ey) {ans = min(ans,k);f = 1;return ;}
    for (int i = 0;i < 4;i++)
    {
        int xx = x + fx[i],yy = y + fy[i];
        if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && a[xx][yy])
        {
            a[xx][yy] = 0;
            int now = 0;
            if (i != t)
                now = 1;
            if (t == -1)
                now = 0;
            dfs(xx,yy,i,k+now);
            a[xx][yy] = 1;
        }
    }
}

void solve()
{
    ans = 2e9;
    scanf("%lld",&n);
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= n;j++)
        {
            cin >> aa[i][j];
            if (aa[i][j] == '.')
                a[i][j] = 1;
            if (aa[i][j] == 'A')
                sx = i,sy = j;
            if (aa[i][j] == 'B')
                ex = i,ey = j,a[i][j] = 1;
        }
    dfs(sx,sy,-1,0);
    if (f) printf("%lld",ans);
    else printf("-1");
}

signed main()
{
    solve();
    printf("\n");
    return 0;
}

by elmt @ 2024-08-09 18:09:36

@dhlzzsx 之前的方向有啥错吗，为啥会t

by dhlzzsx @ 2024-08-10 20:44:24

@elmt 这个错误很玄学

by VictorTang @ 2024-08-14 20:23:34

@dhlzzsx 不太理解，这是为啥？居然过了！！！

by tommy24 @ 2024-09-25 19:18:43

我知道为什么改方向数组会被卡了。用了修改的的方向数组(右下左上)可以第一时间搜到答案，但如果改了方向数组(左上右下)就会搜到其他地方再搜回来，就会超时！ 还是不能写暴力。