Simple and clear solution c++


#1

int n = A.size() , m = A[0].length() , k = B.length();
int dp[n][m][k+1];
memset(dp,0,sizeof(dp));
for(int r = 0;r < n; r++){
for(int c = 0; c < m; c++){
dp[r][c][0] = 1;
}
}
vector<pair<int,int>> change = {{1, 0} , {0 , 1} ,{-1 ,0 }, {0,-1}};

auto check = [&](int r, int c, int i){
    return (r>=0 && r<n) && (c>=0 && c<m) && (A[r][c] == B[i]);
};
for(int i = 0;i < k;i++){
    for(int r = 0;r < n; r++){
        for(int c = 0; c < m; c++){
            if(!dp[r][c][i]) continue;
            
            for(auto [dr,dc] : change){
                int row = r - dr , col = c - dc;
                if(check(row,col,i)){
                    dp[row][col][i+1] = 1;
                }
            } 
        }
    }
}
for(int r = 0;r < n; r++){
    for(int c = 0; c < m; c++){
        if(dp[r][c][k]){
            return 1;
        }
    }
}
return 0;