只萌不新蒟蒻求助dfs
  • 板块P2802 回家
  • 楼主Water_Cows
  • 当前回复13
  • 已保存回复13
  • 发布时间2020/5/16 22:36
  • 上次更新2023/11/7 02:18:53
查看原帖
只萌不新蒟蒻求助dfs
107253
Water_Cows楼主2020/5/16 22:36

rt,我现在菜的连橙题都不会做了/kk

#include <cstdio>
using namespace std;

int n, m, a[11][11], vis[11][11];
int q1, q2, z1, z2, ans = 1e9 ,flag;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

inline int min(int x, int y) {return x<y? x:y;}

inline void dfs(int now1, int now2, int z, int HP)
{
    if(flag == 1) return ;
    if(HP == 0) return ;

    if(now1 == z1 && now2 == z2)
    {
        ans = min(ans, z);
        return ;
    }
    for(int i=0; i<4; i++)
    {
        int p1 = now1 + dx[i];
        int p2 = now2 + dy[i];
        
        if(p1 > n || p2 > m) continue;
        if(p1 < 1 || p2 < 1) continue;
        if(vis[p1][p2]) continue;
        if(a[p1][p2] == 0) continue;
        if(a[p1][p2] == 4) HP = 6;
        if(HP == 1) return ;

        vis[p1][p2] = 1;
        dfs(p1, p2, z + 1, HP - 1);
        vis[p1][p2] = 0;
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            scanf("%d", &a[i][j]);
            if(a[i][j] == 2) q1 = i, q2 = j;
            if(a[i][j] == 3) z1 = i, z2 = j;
        }
    }

    dfs(q1, q2, 0, 6);

    if(ans != 1e9) printf("%d\n", ans);
    else puts("-1");
    return 0;
}

码风比较良心,拒绝无意义回复

2020/5/16 22:36
加载中...