PROBLEM LINK:
Practice Link
Aliens Vs Humans
Author: hellb0y_suru
PROBLEM:
Given a matrix n*m, which consist of some free cells and some cells being occupied by mines, an operation is defined as moving a mine from its current position denoted by ( x, y ) to either of the 4 adjacent neighbour cells. After that, we want to know the maximum number of free cells in our matrix, by applying the given operation on a mine at most once.
PREREQUISITES:
- Dynamic Programming with bit-masking
DIFFICULTY:
MEDIUM
EXPLANATION:
Let us assume that n \leq m. (If this is not the case then we will rotate the matrix because n*m\leq 40)
Let dp[i][currMask][nextMask] be the minimum number of occupied cells in the first i-th columns with the restrictions that the i-th column is described by currMask and i+1-st column is described by nextMask (ones correspond to occupied cells and zeroes correspond to free cells). To make a transition from dp[i-1][-][currMask] we can iterate over all possible masks for the i-1-st column, check whether we can distribute mines in i th column knowing the nextMask for i+1-st and currMask for i-st column respectively and find the minimal value of dp[i-1][-][currMask] for all such masks.
So our final answer will be, minimum value of n*m - dp[m][-][0] , where ’ - ’ denotes all possible masks.
Time complexity : O( m*n* 2^{3*n} ) for each test case.
SOLUTION:
Setter's Solution in C++
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define oo 1000000000000000000
#define forr(i,n) for(int i=0;i<n;i++)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define FF first
#define SS second
#define mem(a,v) memset(a,v,sizeof(a))
#define pb push_back
#define popcount(x) __builtin_popcount(x)
using namespace std;
vector<vector<int>> v;
bool valid(const int &last,const int &cur,const int &next,const int &n,const int &j){
forr(i,n){
if(!((1<<i)&cur) && v[i][j]){
bool f = 0;
if( i && ((1<<(i-1))&cur) ) f = 1;
else if( i+1<n && ((1<<(i+1))&cur) ) f = 1;
else if((1<<i)&last) f = 1;
else if((1<<i)&next) f = 1;
if(!f) return false;
}
}
return true;
}
void __sol(){
int n,m; cin >> n >> m;
vector<vector<int>> temp(n,vector<int>(m+1,0));
forr(i,n) forr(j,m) cin >> temp[i][j+1];
if(n>m){
v.assign(m,vector<int>(n+1,0));
forr(i,n) forr(j,m) v[j][i+1] = temp[i][j+1];
swap(n,m);
}
else v = temp;
int dp[m+2][1<<n][1<<n];
forr(i,m+2) forr(j,1<<n) forr(k,1<<n) dp[i][j][k] = INT_MAX/1000;
for(int i=1;i<=m;i++){
forr(pm,1<<n){
forr(nm,1<<n){
forr(lm,1<<n){
if(i==1 && valid(0,pm,nm,n,i)) dp[i][pm][nm] = min( dp[i][pm][nm], popcount(pm) );
else if(i==m && valid(lm,pm,0,n,i)) dp[i][pm][0] = min(dp[i][pm][0], popcount(pm) + dp[i-1][lm][pm] );
else if(i!=1 && i!=m && valid(lm,pm,nm,n,i)) dp[i][pm][nm] = min(dp[i][pm][nm] , popcount(pm) + dp[i-1][lm][pm]);
}
}
}
}
int ans = INT_MAX/1000;
forr(i,1<<n) ans = min(ans,dp[m][i][0]);
cout << n*m - ans <<"\n";
return;
}
int main(){
fastio;
int tc=1; cin >> tc;
while(tc--) __sol();
return 0;
}