萌新刚学OI求条鸡忆化搜索
查看原帖
萌新刚学OI求条鸡忆化搜索
486727
IaLWH楼主2024/8/12 21:02

本地过了提交WA

#include<stdio.h>
#include<string.h>
#define xd (x+dx[i])
#define yd (y+dy[i])
int n,m,sx,sy,gx,gy,dp[64][64];
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
char a[64][64];

void dfs(int x,int y){
	if(a[x][y]=='#')return;
	if(dp[x][y]<1919810)return;
	dp[x][y]=114514;
	for(int i=0;i<4;i++){
		if(xd>=0&&xd<n&&yd>=0&&yd<m){
			dfs(xd,yd);
			if(dp[xd][yd]<dp[x][y])
				dp[x][y]=dp[xd][yd];
		}
	}
	dp[x][y]++;
}
int main(){
	memset(dp,0x3f,sizeof(dp));
	scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&gx,&gy);
	for(int i=0;i<n;i++)
		scanf("%s",a[i]);
	sx--;sy--;gx--;gy--;
	dp[gx][gy]=0;
	dfs(sx,sy);
	printf("%d\n",dp[sx][sy]);
	return 0;
}
2024/8/12 21:02
加载中...