#include <cmath>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll n,m,t;
ll f[1005][30][30];
ll a[1005];
int main(){
	freopen("lock.in","r",stdin);
	freopen("lock.out","w",stdout);
	cin>>n>>m>>t;
	for(ll i=1;i<t;i++){
		cin>>a[i];
	}
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<=m;j++){
			f[0][i][j]=1;
		}
	}
	for(ll i=1;i<=t;i++){
		for(ll x=1;x<=n;x++){
			for(ll y=1;y<=m;y++){
				for(ll lx=1;lx<=n;lx++){
					for(ll ly=1;ly<=m;ly++){
						if(abs(x-lx)+abs(y-ly)<=a[i-1]){
							//                            cout<<i<<":"<<x<<" "<<y<<" "<<lx<<" "<<ly<<" "<<f[i-1][lx][ly]<<endl;
							f[i][x][y]=(f[i][x][y]+f[i-1][lx][ly])%mod;
						}
					}
				}
			}
		}
	}
	ll ans=0;
	//    for(ll i=1;i<=t;i++){
	//        for(ll x=1;x<=n;x++){
	//            for(ll y=1;y<=m;y++){
	//                cout<<f[i][x][y]<<" ";
	//            }
	//            cout<<endl;
	//        }
	//        cout<<endl;
	//    }
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<=m;j++){
			ans+=f[t][i][j];
			ans%=mod;
		}
	}
	cout<<ans<<endl;
	return 0;
}

考虑$dp$

$f_{i,x,y}$ 表示前 $i$ 个，最后一个在 $x,y$ 的方案数

转移就很简单了：遍历上一个，判断距离是否合法，合法转移

代码如下：

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll n,m,t;
ll f[1005][30][30];
ll a[1005];
int main(){
	freopen("lock.in","r",stdin);
	freopen("lock.out","w",stdout);
	cin>>n>>m>>t;
	for(ll i=1;i<t;i++){
		cin>>a[i];
	}
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<=m;j++){
			f[0][i][j]=1;
		}
	}
	for(ll i=1;i<=t;i++){
		for(ll x=1;x<=n;x++){
			for(ll y=1;y<=m;y++){
				for(ll lx=1;lx<=n;lx++){
					for(ll ly=1;ly<=m;ly++){
						if(abs(x-lx)+abs(y-ly)<=a[i-1]){
							//                            cout<<i<<":"<<x<<" "<<y<<" "<<lx<<" "<<ly<<" "<<f[i-1][lx][ly]<<endl;
							f[i][x][y]=(f[i][x][y]+f[i-1][lx][ly])%mod;
						}
					}
				}
			}
		}
	}
	ll ans=0;
	//    for(ll i=1;i<=t;i++){
	//        for(ll x=1;x<=n;x++){
	//            for(ll y=1;y<=m;y++){
	//                cout<<f[i][x][y]<<" ";
	//            }
	//            cout<<endl;
	//        }
	//        cout<<endl;
	//    }
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<=m;j++){
			ans+=f[t][i][j];
			ans%=mod;
		}
	}
	cout<<ans<<endl;
	return 0;
}