珠海网站建设制作设计,珠宝网站模板,网站维护费怎么做分录,无网站营销题目描述
现有一个n∗m大小的矩阵#xff0c;矩阵中的每个元素表示该位置的权值。现需要从矩阵左上角出发到达右下角#xff0c;每次移动只能向上下左右移动一格#xff08;不允许移动到曾经经过的位置#xff09;。求最后到达右下角时路径上所有位置的权值之和的最大值。…
题目描述
现有一个n∗m大小的矩阵矩阵中的每个元素表示该位置的权值。现需要从矩阵左上角出发到达右下角每次移动只能向上下左右移动一格不允许移动到曾经经过的位置。求最后到达右下角时路径上所有位置的权值之和的最大值。
输入描述
第一行两个整数n、m2≤n≤5,2≤m≤5分别表示矩阵的行数和列数
接下来n行每行m个整数−100≤整数≤100表示矩阵每个位置的权值。
输出描述
一个整数表示权值之和的最大值。
输入样例
2 2 1 2 3 4
输出样例
8
代码
#includebits/stdc.h
using namespace std;
int vis[1005][1005],Map[1005][1005];
int n,m,Max 0;
int dx[4] {0,0,1,-1};
int dy[4] {1,-1,0,0};
bool isValid(int x,int y){return x0xny0ym!vis[x][y];
}
void dfs(int x,int y,int nowValue){if(xn-1ym-1){if(nowValueMax){Max nowValue;}return;}vis[x][y] 1;for(int i 0;i4;i){int nextx xdx[i];int nexty ydy[i];if(isValid(nextx,nexty)){int nextValue nowValueMap[nextx][nexty];dfs(nextx,nexty,nextValue);}}vis[x][y] 0;}
int main() {cinnm;for(int i 0;in;i){for(int j 0;jm;j){cinMap[i][j];}}dfs(0,0,Map[0][0]);coutMaxendl;
}
