摄影网站公司,做本地团购网站怎么样,平面设计空间构成图片,软文世界官网题目描述
东九日在学习dp的时候#xff0c;解决了经典的矩阵最大路径和问题#xff1b;
他向队友小夨阐述他的感悟#xff0c;dp要做的就是感受解空间#xff1b;
为了防止东九日赛上犯病#xff0c;小夨决定出一道改编版检查东九日的实力。 以上为题目背景#xff1b…题目描述
东九日在学习dp的时候解决了经典的矩阵最大路径和问题
他向队友小夨阐述他的感悟dp要做的就是感受解空间
为了防止东九日赛上犯病小夨决定出一道改编版检查东九日的实力。 以上为题目背景
给定一个 n 行 m 列的矩阵 a初始的时候你在矩阵左上角 (1,1) 的位置即第 1 行第 1 列你想要通过移动到达矩阵右下角 (n,m)的位置即第 n 行第 m 列
若你在位置 (x,y)那么你可以进行以下移动 ①向左移动到达位置 (x,y−1) ②向右移动到达位置 (x,y1) ③向上移动到达位置 (x−1,y) ④向下移动到达位置 (x1,y)
注意每个位置可以重复到达多次但你不可以走出矩阵 假设你从位置 (1,1) 到达位置(n,m) 经过了这样一条长度为 k 路径(x1,y1)→(x2,y2)→...→(xk−1,yk−1)→(xk,yk)那么这条路径的权值就定义为 ax1,y1 ax2,y2 ... axk−1,yk−1 axk,yk 表示 “按位与” 请你求出所有的从位置 (1,1) 到位置 (n,m)的路径中权值最大的那条路径其对应的权值是多少 输入描述:
第一行输入两个整数 n,m (1≤n×m≤10^5)表示矩阵的大小为 n 行m 列
接下来输入 n 行每一行输入 m 个整数 ai,1,ai,2,...,ai,m (0≤ai,j≤10^9)分别表示矩阵的每个位置上元素的值。
输出描述:
输出一个整数ans表示最大的路径权值。 示例1
输入
3 3
1 1 1
0 0 1
0 0 1
输出
1 #includebits/stdc.h
using namespace std;
#define fp(i,a,b) for(int ia;ib;i)
#define PII pairint,int
//typedef long long ll;
#define int long long
typedef double db;
const int N1e610;
const int M505;
const int mod1e97;
int n,m;
int a[N];
bool tr[N],u[N];
int id(int x,int y)
{return (x-1)*my;
}
void dfs(int x,int y)
{if(!tr[id(x,y)])return;if(u[id(x,y)])return;u[id(x,y)]1;if(x1)dfs(x-1,y);if(xn)dfs(x1,y);if(y1)dfs(x,y-1);if(ym)dfs(x,y1);
}
bool check(int mid)
{memset(u,0,sizeof u);memset(tr,0,sizeof tr);for(int i1;in*m;i){if((a[i]mid)mid)tr[i]1;}dfs(1,1);return u[n*m];
}
void solve()
{ cinnm;int ans0;fp(i,1,n){fp(j,1,m){cina[id(i,j)];}}for(int t30;t0;t--){if(check(ans|(1t)))ans|1t;}coutans\n;
}
signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int T;
// cinT;T1;while(T--){solve();}return 0;
}
思路从2^30一直到2^0,看1*1能不能到n*m。
