深搜?递推(动态规划)!
2024-02-14 23:01:43
发布于:广东
13阅读
0回复
0点赞
此处说明,要两个数组是因为如果只有一个的话会出现反复加的情况qwq
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
long long dp1[105][105], dp2[105][105];//要两个数组
char mp[105][105];
int dir[4][2] = {-1, 0, 0, -1, 0, 1, 1, 0};//
int n, m, t, x1, y1, x2, y2;
bool check(int x, int y){//check函数
if(x < 1 || x > n) return 0;
if(y < 1 || y > m) return 0;
if(mp[x][y] == '*') return 0;
return 1;
}
int main(){
cin >> n >> m >> t;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> mp[i][j];
}
}cin >> x1 >> y1 >> x2 >> y2;
dp1[x1][y1] = 1;
while(t--){
memset(dp2, 0, sizeof(dp2));//好习惯,清空数组qwq
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(dp1[i][j]){//判断,节省时间
for(int k = 0; k < 4; k++){
int xx = i + dir[k][0], yy = j + dir[k][1];//xxyy
if(check(xx, yy)){
dp2[xx][yy] += dp1[i][j];//如果符合,就扩到其他方向
}
}
}
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
dp1[i][j] = dp2[i][j];//把数组2复制回数组1
}
}
}cout << dp1[x2][y2];//输出
return 0;
}
也是很ez好吧
这里空空如也
有帮助,赞一个