做淘宝网站需要多少钱,网站开发的有哪些好的软件,网站开发网络结构图,建材招商网题目#xff1a;vj地址 思路#xff1a;dp[i][j][k]代表 以i#xff0c;j结尾 有k长度的路径数量#xff0c;k最大等于4#xff0c;如果k超过4#xff0c;也是等于4. 那么转移#xff1a;dp[i][j][k]{dp[x][y][k-1]}(x,y满足a[x][y]1a[i][j]); 如果k4,还有dp[i][j][k]{d…题目vj地址 思路dp[i][j][k]代表 以ij结尾 有k长度的路径数量k最大等于4如果k超过4也是等于4. 那么转移dp[i][j][k]{dp[x][y][k-1]}(x,y满足a[x][y]1a[i][j]); 如果k4,还有dp[i][j][k]{dp[x][y][k]}(x,y满足a[x][y]1a[i][j]);
细节见代码。
#includebits/stdc.h
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define FILL(a,b) (memset(a,b,sizeof(a)))
#define re register
#define lson rt1
#define rson rt1|1
#define lowbit(a) ((a)-(a))
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define fi first
#define rep(i,n) for(int i0;(i)(n);i)
#define rep1(i,n) for(int i1;(i)(n);i)
#define se secondusing namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint,int pii;
int dx[4] {-1,1,0,0},dy[4] {0,0,1,-1};
const ll mod1e97;
const ll N 2e610;
const double eps 1e-4;
const double piacos(-1);
ll gcd(int a,int b){return !b?a:gcd(b,a%b);}
ll dp[1100][1100][5];
ll a[1100][1100];
ll n,m;
bool check1(ll x,ll y)//检查是否能转移
{for(ll i0;i4;i){ll x1xdx[i],y1ydy[i];if(x10||x1n||y10||y1m) continue;if(a[x][y]-1a[x1][y1]) return 0;}return 1;
}
bool check2(ll x,ll y)
{for(ll i0;i4;i){ll x1xdx[i],y1ydy[i];if(x10||x1n||y10||y1m) continue;if(a[x][y]1a[x1][y1]) return 0;}return 1;
}
ll dfs(ll i,ll j,ll k)//记忆化搜索
{if(k1){if(check1(i,j)) return 1;else return 0;}if(dp[i][j][k]!-1) return dp[i][j][k];ll ansdp[i][j][k];ans0;for(ll w0;w4;w){ll x1idx[w],y1jdy[w];if(x10||x1n||y10||y1m) continue;if(a[x1][y1]1a[i][j]){ansdfs(x1,y1,k-1);if(k4) ans(ansdfs(x1,y1,4))%mod;//k4时的特判转移条件}}return ans;
}
int main()
{#ifdef LOCALfreopen(in.txt, r, stdin);#endifmemset(dp,-1,sizeof dp);scanf(%lld%lld,n,m);for(int i1;in;i)for(int j1;jm;j) scanf(%lld,a[i][j]);ll ans0;for(int i1;in;i){for(int j1;jm;j){if(check2(i,j)) ans(ansdfs(i,j,4))%mod;//满足转移条件时才能加}}coutansendl;return 0;
}
