量子奶牛 题目ID：9733

常规
1

. 量子奶牛

题目ID：9733必做题100分

最新提交：

Time Limit Exceeded

90 分

历史最高：

Time Limit Exceeded

90 分

时间限制: 1000ms

空间限制: 524288kB

题目描述

约翰 T 秒前看到奶牛在 (x1,y1) 处，而现在看到奶牛在 (x2, y2) 处。毫无疑问，奶牛在这 T 秒内发生了量子隧穿效应。已知奶牛每秒可以移动一步到与当前格子四连通的格子处（除非目标格子处有障碍），现在约翰想知道奶牛有几种可能的隧穿路径。

（其实就是求从(x1,y1)走到(x2,y2)恰好过了 T 秒的路径数量）

输入格式：

第一行包含 3个用空格隔开的整数 n，m，T。

接下来 n 行每行一个长度为 m 的字符串。‘.’ 是空地，'*'是障碍

最后一行 4 个整数 x1, y1, x2, y2。

输出格式：

输出一行一个整数表示答案。

样例输入：

4 5 6
...*.
...*.
.....
.....
1 3 1 5

样例输出：

1

数据规模：

2≤N,M≤100，0<T≤15。

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int n,m,t,x,y,fx,fy,ans=0;
char a[N][N];
bool vis[N][N];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
void dfs(int x,int y,int cnt){
	if(cnt==t){
//		cout<<-1<<endl;
//		cout<<x<<" "<<y<<endl;
		if(x==fx&&y==fy){
//			cout<<-1<<endl;
			ans++;
		}
		return ;
	}
	for(int i=0;i<4;i++){
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx<1||ny<1||nx>n||ny>m||a[nx][ny]=='*')continue;
		dfs(nx,ny,cnt+1);
	}
}
int main(){
	cin>>n>>m>>t;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		} 
	}
	cin>>x>>y>>fx>>fy;
	dfs(x,y,0);
	cout<<ans;
	return 0;
}

那位大佬能帮我看看怎么剪枝啊

2 个赞