TLE！！！

常规
21

那就奇怪了。。

1 个赞
22

你可以尝试下

2 个赞
23

image
image1176×264 18.1 KB

1 个赞
24

更低了

25

我也20了。。

1 个赞
26

所以简直到底咋写呢

2 个赞
27

emm
把你中间的

if(nx<1||nx>n||ny<1||ny>m||mp[nx][ny]=='*'||vis[nx][ny])
		{
			continue;	
		}
		vis[nx][ny]=1;
		step++;
		dfs(nx,ny);
		vis[nx][ny]=0;

改成了

if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&mp[nx][ny]=='.'&&!vis[nx][ny])
		{
			vis[nx][ny]=1;
		step++;
		dfs(nx,ny);
		vis[nx][ny]=0;
		}

但是还是没过

1 个赞
28

666

2 个赞
29 
#include<bits/stdc++.h>
using namespace std;
int n,m,t,cnt;
char a[101][101];
struct node{
    int x,y,t;
    node(){};
    node(int xx,int yy,int tt){
        x=xx,y=yy,t=tt;
    }
}st,ed;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}},f[55][55][22];
void bfs(node s){
    queue<node> q;
    q.push(s);
    while(!q.empty()){
        node now=q.front();
        q.pop();
        if(now.t>ed.t)
            return;
        for(int i=0;i<4;i++){
            int tx=now.x+dir[i][0],ty=now.y+dir[i][1];
            if(a[tx][ty]=='.'){
                node v=node(tx,ty,now.t+1);
                if(abs(v.x-ed.x)+abs(v.y-ed.y)>t-v.t)continue;
                f[tx][ty][now.t+1]+=f[now.x][now.y][now.t];
                if(f[tx][ty][now.t+1]-f[now.x][now.y][now.t]>0)continue;
                q.push(v);
            }
        }
    }
    return;
}
int main(){
    cin>>n>>m>>t;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    f[a][b][0]=1;
    st=node(a,b,0);
    ed=node(c,d,t);
    bfs(st);
    cout<<f[c][d][t]<<endl;
    return 0;
}

这是我的思路，有用给个解决方案吧
（仅供参考）

1 个赞
30

额我就是用的这个

1 个赞
31

bfs+记忆化
他说不行

1 个赞
32

所以解决方案给谁

1 个赞
33

给我呗

2 个赞
34

6~

1 个赞
35

谢谢你

1 个赞
36

bfs的复杂度跟dfs一样吧，而且bfs一般是求最短路径，而dfs一般是求方案总数

1 个赞
37

这题求的就是方案数

1 个赞
38

可是bfsAC了

1 个赞
39

我知道啊

1 个赞
40

这种啥意思

1 个赞