这题只能用广搜做吗?
  • 板块CF1063B Labyrinth
  • 楼主cui_can
  • 当前回复6
  • 已保存回复6
  • 发布时间2021/7/17 10:01
  • 上次更新2023/11/4 14:32:09
查看原帖
这题只能用广搜做吗?
444267
cui_can楼主2021/7/17 10:01

DFS错了

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,r,c,x,y,ans;
char ma[2005][2005];
bool visit[2005][2005];
int cost[2005][2005];
bool able(int a,int b){
	if(visit[a][b]||ma[a][b]=='*'||a<1||b<1||a>n||b>m)
		return 0;
	else
		return 1;
}
bool best(int a,int b,int p,int q){
	if(p+q>cost[a][b])return 1;
	else return 0;
}
void dfs(int r,int c,int x,int y){
	visit[r][c]=1;
	cost[r][c]=x+y;
	ans++;
	if(x>0){
		if(able(r,c-1))
			dfs(r,c-1,x-1,y);
	}
	if(y>0){
		if(able(r,c+1))
			dfs(r,c+1,x,y-1);
	} 
	if(able(r-1,c))
		dfs(r-1,c,x,y);
	if(able(r+1,c))
		dfs(r+1,c,x,y); 
	return;
}
int main(){
	scanf("%d%d%d%d%d%d",&n,&m,&r,&c,&x,&y);
	for(int i=1;i<=n;i++)
		scanf("%s",ma[i]+1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			visit[i][j]=0;
	dfs(r,c,x,y);
	printf("%d\n",ans);
	return 0;
}

CF

2021/7/17 10:01
加载中...