对样例输出0 记忆化DFS求助
  • 板块P1605 迷宫
  • 楼主幽灵特工
  • 当前回复10
  • 已保存回复10
  • 发布时间2021/2/22 20:35
  • 上次更新2023/11/5 02:52:08
查看原帖
对样例输出0 记忆化DFS求助
332549
幽灵特工楼主2021/2/22 20:35
#include<bits/stdc++.h>
using namespace std;
int n,m,t;
int s[6][6],vis[6][6];
int sx,sy,fx,fy;
int DFS(int x,int y){
	int ans=0;
	vis[x][y]=1;
	if(vis[x][y]!=0)return s[x][y];
	if(x==fx&&y==fy){
		ans++;s[x][y]=ans;return s[x][y];
	}
	if(s[x][y]==-1)return 0;
	if(x+1<=n&&!s[x+1][y])ans+=DFS(x+1,y);
	if(y+1<=m&&!s[x][y+1])ans+=DFS(x,y+1);
	if(x-1>=1&&!s[x-1][y])ans+=DFS(x-1,y);
	if(y-1>=1&&!s[x][y-1])ans+=DFS(x,y-1);
	s[x][y]+=ans;
	return s[x][y];
}
int main(){
	cin>>n>>m>>t;
	cin>>sx>>sy>>fx>>fy;
	int a,b;
	while(t--){
		cin>>a>>b;
		s[a][b]=-1;
	}
	cout<<DFS(sx,sy);
} 
2021/2/22 20:35
加载中...