88 pts 记搜爆炸求条
查看原帖
88 pts 记搜爆炸求条
926886
kind_Ygg楼主2024/7/20 09:55
#include<bits/stdc++.h>
#define time r
using namespace std;
int n,m;
int time;
char a;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
bool s[105][105];
int sx,sy,fx,fy;
//int ans;
int js[105][105][20];
int dfs(int x,int y,int now)
{
	if(js[x][y][now]!=-1) return js[x][y][now];
	if(abs(x-fx)+abs(y-fy)>time-now)
		return js[x][y][now]=0;
	if(now==time)
	{
		if(x==fx&&y==fy)
			return js[x][y][now]=1;
		else 
			return js[x][y][now]=0;
	}
	int ans=0;
	for(int i=0;i<4;i++)
	{
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!s[xx][yy])
			ans+=dfs(xx,yy,now+1);
	}
	ans+=dfs(x,y,now+2);
	return ans;
}
int main()
{
	cin>>n>>m;
	cin>>time;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a;
			if(a=='.')
				s[i][j]=0;
			else
				s[i][j]=1;
		}
	}
	memset(js,-1,sizeof(js));
	cin>>sx>>sy>>fx>>fy;
	cout<<dfs(sx,sy,0);
	return 0;
}
2024/7/20 09:55
加载中...