求大佬看看,dfs 30pts,其他全部tle,能不能再剪一下枝
查看原帖
求大佬看看,dfs 30pts,其他全部tle,能不能再剪一下枝
841612
xian_love楼主2024/7/21 16:56
//不就是迷宫问题?
#include<bits/stdc++.h>
using namespace std;
int n, m;
int hx,hy;
const int N = 410;
int res[N][N]; //存答案数组
bool st[N][N]; //存走没走过
int cnt = 1e9;
int step[N][N];
int dx[] = {1,2,2,1,-1,-2,-2,-1};
int dy[] = {2,1,-1,-2,-2,-1,1,2};
//枚举所有(x,y)到(ansx,asny)的路线,找到其中最短的存入答案数组中
void dfs(int x,int y,int ansx,int ansy,int ans)
{
    if(x<=0||x>n||y<=0||y>m)return;
    if(st[x][y])return;
    if(ans > cnt)return; 
    //if(ans>step[x][y])return;
    if(x == ansx&&y == ansy)
    {
        cnt = min(cnt,ans);
        //step[ansx][ansy] = cnt;
        return;
    }
    //枚举马走的八个日字
    for(int i =0;i<8;i++)
    {
        int a = x + dx[i];
        int b = y + dy[i];
        if(!st[a][b]&&a>0&&a<=n&&b>0&&b<=m)
        {
            st[x][y] = true;
            dfs(a,b,ansx,ansy,ans+1);
            st[x][y] = false;
        }
    }
}
int main()
{
    cin>>n>>m;
    cin>>hx>>hy;
    for(int i =1;i<=n;i++)
        for(int j =1;j <=m;j++)
        {
            cnt = 1e9;
            memset(step,1e9,sizeof(step));
            dfs(hx,hy,i,j,0);
            if(cnt == 1e9)res[i][j] = -1;
            else res[i][j] = cnt;
        }
    for(int i=1;i<=n;i++)
    {
        
        for(int j=1;j<=m;j++)
        {
            cout<<left<<setw(5)<<res[i][j];
        }
        cout<<endl;
    }
    return 0;
}
2024/7/21 16:56
加载中...