1928. 灵能矩阵 -- dp,bitmask

 1 

 #include 
 2 using namespace std;
 3 using LL = long long;
 4 int mp[505][505], ans[505][505];
 5 bool dp[505][505];
 6 int n, m;
 7 int main() {
 8     cin >> n >> m;
 9     for (int i = 1; i <= n; i++) {
10         for (int j = 1; j <= m; j++) {
11             cin >> mp[i][j];
12         }
13     }
14     //输入，不多说
15     int res = 0;
16     /*思路简析：要求按位与的最大值，就需要保证从矩阵的左上角到右下角的过程中，
17     存在二进制中相同的一位都是1，如此按位与之后才能保证最大的值*/
18     for (int k = 30; k >= 0; k--) {//从(1<<30)开始找这个 1,贪心的思路
19         dp[1][0] = 1;//初始化
20         res += (1 << k);//答案肯定是001000101100...这种形式，所以假设先有路径，就先加上
21         for (int i = 1; i <= n; i++) {
22             for (int j = 1; j <= m; j++) {
23                 //重要性质：按位与 & 是严格不增的，故可用这个性质判断
24                 /*if语句的意思: 如果此时的mp[i][j]和当前答案按位与之后，答案不变，并且该位置的左边或者上面有这个1，说明能够转移*/
25                 if (((mp[i][j] & res) == res) && (dp[i - 1][j] || dp[i][j - 1]))
26                     dp[i][j] = 1;
27                 else/*否则不能转移*/
28                     dp[i][j] = 0;
29             }
30         }
31         if (!dp[n][m]) res -= (1 << k);//如果不存在这样的连通路径就把它减掉
32 
33     }
34 
35     cout << res << endl;
36     return 0;
37 }