关键词：
题目描述
Searching for the very best grass, the cows are travelling about the pasture which is represented as a grid with N rows and M columns (2 <= N <= 100; 2 <= M <= 100). Keen observer Farmer John has recorded Bessie‘s position as (R1, C1) at a certain time and then as (R2, C2) exactly T (0 < T <= 15) seconds later. He‘s not sure if she passed through (R2, C2) before T seconds, but he knows she is there at time T.
FJ wants a program that uses this information to calculate an integer S that is the number of ways a cow can go from (R1, C1) to (R2, C2) exactly in T seconds. Every second, a cow can travel from any position to a vertically or horizontally neighboring position in the pasture each second (no resting for the cows). Of course, the pasture has trees through which no cow can travel.
Given a map with ‘.‘s for open pasture space and ‘*‘ for trees, calculate the number of possible ways to travel from (R1, C1) to (R2, C2) in T seconds.
奶牛们在被划分成N行M列(2 <= N <= 100; 2 <= M <= 100)的草地上游走， 试图找到整块草地中最美味的牧草。Farmer John在某个时刻看见贝茜在位置 (R1, C1)，恰好T (0 < T <= 15)秒后，FJ又在位置(R2, C2)与贝茜撞了正着。 FJ并不知道在这T秒内贝茜是否曾经到过(R2, C2)，他能确定的只是，现在贝茜 在那里。 设S为奶牛在T秒内从(R1, C1)走到(R2, C2)所能选择的路径总数，FJ希望有 一个程序来帮他计算这个值。每一秒内，奶牛会水平或垂直地移动1单位距离（ 奶牛总是在移动，不会在某秒内停在它上一秒所在的点）。草地上的某些地方有 树，自然，奶牛不能走到树所在的位置，也不会走出草地。 现在你拿到了一张整块草地的地形图，其中‘.‘表示平坦的草地，‘*‘表示 挡路的树。你的任务是计算出，一头在T秒内从(R1, C1)移动到(R2, C2)的奶牛 可能经过的路径有哪些。
输入输出格式
输入格式：
第1 行: 3 个用空格隔开的整数：N，M，T 。 第2..N+1 行: 第i+1 行为M 个连续的字符，描述了草地第i 行各点的情况，保证字符是‘.‘和‘*‘中的一个。 第N+2 行: 4 个用空格隔开的整数：R1，C1，R2，C2 。
输出格式：
第1 行: 输出S，含义如题中所述。
输入输出样例
说明
样例说明:
草地被划分成4 行5 列，奶牛在6 秒内从第1 行第3 列走到了第1 行第5 列。
奶牛在6 秒内从(1,3)走到(1,5)的方法只有一种（绕过她面前的树）
思路：dfs+剪枝
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXN 110 using namespace std; int n,m,s,ans; int sx,sy,tx,ty; int map[MAXN][MAXN]; int dx[4]=1,-1,0,0; int dy[4]=0,0,1,-1; void dfs(int x,int y,int tot) if(tot>s) return ; if(x<1||x>n||y<1||y>m||map[x][y]) return ; if(abs(x-tx)+abs(y-ty)>s-tot) return ; if(x==tx&&y==ty&&s==tot) ans++; return ; dfs(x+1,y,tot+1); dfs(x-1,y,tot+1); dfs(x,y+1,tot+1); dfs(x,y-1,tot+1); int main() scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) char s;cin>>s; if(s==‘.‘) map[i][j]=0; else map[i][j]=1; scanf("%d%d%d%d",&sx,&sy,&tx,&ty); dfs(sx,sy,0); cout<<ans;
思路：记忆化搜索。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXN 110 using namespace std; int n,m,s,ans; int sx,sy,tx,ty; int map[MAXN][MAXN],f[MAXN][MAXN][20]; int dx[4]=1,-1,0,0; int dy[4]=0,0,1,-1; void dfs(int x,int y,int tot) if(f[x][y][tot]) return ; if(tot>s) return ; if(abs(x-tx)+abs(y-ty)>s-tot) return ; if(x==tx&&y==ty&&tot==s) f[x][y][tot]=1; return ; for(int i=0;i<4;i++) int cx=x+dx[i]; int cy=y+dy[i]; if(cx>=1&&cx<=n&&cy>=1&&cy<=m&&!map[cx][cy]) dfs(cx,cy,tot+1); f[x][y][tot]+=f[cx][cy][tot+1]; int main() scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) char s;cin>>s; if(s==‘.‘) map[i][j]=0; else map[i][j]=1; scanf("%d%d%d%d",&sx,&sy,&tx,&ty); dfs(sx,sy,0); cout<<f[sx][sy][0];
洛谷1578：[wc2002]奶牛浴场——题解(代码片段)
https://www.luogu.org/problemnew/show/P1578#sub由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个... 查看详情
记忆化搜索游荡的奶牛
[luogu1535]游荡的奶牛题目描述Searchingfortheverybestgrass,thecowsaretravellingaboutthepasturewhichisrepresentedasagridwithNrowsandMcolumns(2<=N<=100;2<=M<=100).KeenobserverFarmerJohnhasrecordedBess 查看详情
cogs130.[usacomar08]游荡的奶牛[dp]
130.[USACOMar08]游荡的奶牛★☆ 输入文件：ctravel.in 输出文件：ctravel.out 简单对比时间限制：1s 内存限制：128MB奶牛们在被划分成N行M列(2<=N<=100;2<=M<=100)的草地上游走，试图找到整块草... 查看详情
[bzoj]1616:[usaco2008mar]cowtravelling游荡的奶牛
1616:[Usaco2008Mar]CowTravelling游荡的奶牛TimeLimit: 5Sec MemoryLimit: 64MBSubmit: 1312 Solved: 736[Submit][Status][Discuss]Description奶牛们在被划分成N行M列(2<=N<=100 查看详情
bzoj1827洛谷2986[usaco10mar]伟大的奶牛聚集greatcowgather(代码片段)
【题解】 很容易想到暴力做法，枚举每个点，然后对于每个点O(N)遍历整棵树计算答案。这样整个效率是O(N^2)的，显然不行。 我们考虑如果已知当前某个点的答案，如何快速计算它的儿子的答案。 显然选择它的儿子... 查看详情
洛谷p1824进击的奶牛二分答案（求最大的最小值）(代码片段)
题目链接：https://www.luogu.org/problemnew/show/P1824题目描述FarmerJohn建造了一个有N(2<=N<=100,000)个隔间的牛棚，这些隔间分布在一条直线上，坐标是x1,...,xN(0<=xi<=1,000,000,000)。他的C(2<=C<=N)头牛不满于隔间的位置分布，它们为... 查看详情
洛谷p2733家的范围homeontherange(代码片段)
P2733家的范围HomeontheRange题目背景农民约翰在一片边长是N(2<=N<=250)英里的正方形牧场上放牧他的奶牛。(因为一些原因，他的奶牛只在正方形的牧场上吃草。)遗憾的是,他的奶牛已经毁坏一些土地。(一些1平方英里的正方形... 查看详情
洛谷p2915[usaco08nov]奶牛混合起来mixedupcows(代码片段)
P2915[USACO08NOV]奶牛混合起来MixedUpCows题目描述EachofFarmerJohn‘sN(4<=N<=16)cowshasauniqueserialnumberS_i(1<=S_i<=25,000).Thecowsaresoproudofitthateachonenowwearshernumberinagangstamannerengravedin 查看详情
1616:[usaco2008mar]cowtravelling游荡的奶牛
Description奶牛们在被划分成N行M列(2<=N<=100;2<=M<=100)的草地上游走，试图找到整块草地中最美味的牧草。FarmerJohn在某个时刻看见贝茜在位置(R1,C1)，恰好T(0<T<=15)秒后，FJ又在位置(R2,C2)与贝茜撞了正着。FJ并不知道在这T... 查看详情
p1535(代码片段)
P1535P1535记忆化搜索(dp[i][j][t])表示从(i,j)开始走还剩下(t)秒时方案数那么开始时就是(dfs(stx,sty,t))到达(edx,edy,0)时算一种路线那么整个的结构就很清晰了：if(judge(x+1,y))ans+=dfs(x+1,y,t-1);if(judge(x-1,y))ans+=dfs(x-1,y,t-1);if(judge(x,y+ 查看详情
bzoj1616[usaco2008mar]cowtravelling游荡的奶牛
Description奶牛们在被划分成N行M列(2<=N<=100;2<=M<=100)的草地上游走，试图找到整块草地中最美味的牧草。FarmerJohn在某个时刻看见贝茜在位置(R1,C1)，恰好T(0<T<=15)秒后，FJ又在位置(R2,C2)与贝茜撞了正着。FJ并不知道在这T... 查看详情
bzoj1616[usaco2008mar]cowtravelling游荡的奶牛：dp网格型
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1616题意： 有一个n*m的网格。 ‘.‘表示平坦的草地，‘*‘表示挡路的树（不能走）。 有一只奶牛，第0秒时在(r1,c1)，第t秒时在(r1,c2)。 它每一秒钟都会向上下左右... 查看详情
洛谷p1879解题报告(代码片段)
P1879[USACO06NOV]玉米田CornFields题目描述农场主\(John\)新买了一块长方形的新牧场，这块牧场被划分成\(M\)行\(N\)列\((1≤M≤12;1≤N≤12)\)，每一格都是一块正方形的土地。\(John\)打算在牧场上的某几格里种上美味的草，供他的奶牛们享... 查看详情
洛谷p2676超级书架题解(代码片段)
题目传送门题目一看就是贪心。C++福利来了：sort。基本思路就是：要使奶牛最少那么肯定高的奶牛先啦。直接排序一遍（从高到矮）然后while，搞定！#include<bits/stdc++.h>#definelllonglongusingnamespacestd;llN,B,H[20010];boolcmp(intx,inty)retur... 查看详情
洛谷p1578奶牛浴场
P1578奶牛浴场题目描述由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产... 查看详情
洛谷p2345奶牛集会
题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i头奶牛的坐标为Xi，没有两头... 查看详情
洛谷p2345奶牛集会
题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i头奶牛的坐标为Xi，没有两头... 查看详情
洛谷p2345奶牛集会
题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i头奶牛的坐标为Xi，没... 查看详情