C++14(g++5.4) 解法, 执行用时: 501ms, 内存消耗: 2076K, 提交时间: 2020-08-09 16:11:25

#include<bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
#define Fox ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int mod=1e9+7;
int n,m,t,a,b,c,d,dist,r;
int dp[2][205][205][5];
int dx[]={0,1,-1,0,0},dy[]={0,0,0,1,-1};
int calc(int x,int y){
	return (max(abs(a-x),abs(b-y))<=dist);
}
int main(){
	Fox; 
	cin>>n>>m>>t>>a>>b>>dist>>c>>d;
	dp[0][1][1][0]=1;
	for(int T=1;T<=t;T++){
		r^=1;memset(dp[r],0,sizeof(dp[r]));
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				int v=calc(i,j);
				int rec=dp[!r][i][j][0];
				if(v){
					for(int k=1;k<5;k++){
						dp[r][i][j][0]=(dp[r][i][j][0]+dp[!r][i][j][k])%mod;
						dp[r][i+dx[k]][j+dy[k]][k]=(dp[r][i+dx[k]][j+dy[k]][k]+dp[!r][i][j][k])%mod;
					}
				}
				else for(int k=1;k<5;k++)rec=(rec+dp[!r][i][j][k])%mod;
				for(int k=0;k<5;k++)dp[r][i+dx[k]][j+dy[k]][k]=(dp[r][i+dx[k]][j+dy[k]][k]+rec)%mod;
			}
	}
	int ans=0;
	for(int i=0;i<5;i++)ans=(ans+dp[r][c][d][i])%mod;
	cout<<ans;	
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 726ms, 内存消耗: 2152K, 提交时间: 2020-04-03 20:43:35

#include<bits/stdc++.h>
using namespace std;
typedef long long s64;
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int N=200+5,D=1e9+7;
const int fx[5]={-1,1,0,0,0};
const int fy[5]={0,0,-1,1,0};
s64 mi(s64 x,int y=D-2)
{
	s64 ans=1;
	while(y)
	{
		if(y&1) ans=ans*x%D;
		x=x*x%D;
		y>>=1;
	}
	return ans;
}
int dp[2][N][N][5];
int main()
{
	int n,m,t,x1,y1,d,x2,y2;
	cin>>n>>m>>t>>x1>>y1>>d>>x2>>y2;
	dp[0][1][1][4]=1;
	rep(i,1,t)
	{
		bool b=i%2;
		rep(x,1,n)
		rep(y,1,m)
		rep(t,0,4) dp[b][x][y][t]=0;
		rep(x,1,n)
		rep(y,1,m)
		rep(t,0,4)
		if(dp[b^1][x][y][t])
		rep(t2,0,4)
		if(!(max(abs(x-x1),abs(y-y1))<=d&&t2!=4&&t!=4&&t!=t2))
		(dp[b][x+fx[t2]][y+fy[t2]][t2]+=dp[b^1][x][y][t])%=D;
	}
	int ans=0;
	rep(i,0,4) (ans+=dp[t%2][x2][y2][i])%=D;
	cout<<ans;
}