Difficulty
Easy
Prerequisite
Observation
Explanation
Each broken wall increases the number of connected regions of the plane at most by one. Since in the end every single cell must be in the same region as the outside of the prison, there has to be only one connected region, hence the answer is at least nm (because there were nm+1 connected regions at the beginning). To achieve the answer, one can, for example, break the upper wall in every cell.
Author's Solution
#include<bits/stdc++.h>
#define int long long
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
#define N 10000000
#define limit 10000
template <typename T>
void print(T x){cout<<x<<"\n";}
template <typename T1, typename T2>
void print2(T1 x,T2 y){cout<<x<<" "<<y<<"\n";}
template <typename T1, typename T2,typename T3>
void print3(T1 x, T2 y,T3 z){cout<<x<<" "<<y<<" "<<z<<"\n";}
signed main()
{
io;
int test_case;
cin>>test_case;
//test_case=1;
while(test_case--)
{
int a,b;
cin>>a>>b;
print(a*b);
}
}