Explain: This problem says Given an m x n chessboard and finds the number of maximum knights in the chessboard that no two knights attack each other.
In this problem Naturally ans is ( (m*n)+1)/2
Unfortunately 2 differnet special case
Special test case 1:
Now we talk about the special case in this problem if our row or column is 1 then we set max number or knight in our chessboard Example: row = 1 and column = 5, so we can set 5 knights in this chessboard or row = 5 and column = 1 so we can set 5 knights in this chessboard.
For m==1 || n==1 ans is max(n,m)
Special test case 2:
Now we talk about the special case in this problem if our row or column is 2 then we set
we set 2*1 chessboard 2 knights
we set 2*2 chessboard 4 knights
we set 2*3 chessboard 4 knights because of 1*3 and 2*3 number index attack in 1*1 and 2*1 knights
we set 2*4 chessboard 4 knights because of 1*3 and 2*3 number index attack in 1*1 and 2*1 knights and 1*4 and 2*4 number index attack in 1*2 and 2*2 knights
we set 2*5 chessboard 6 knights because of 1*3 and 2*3 number index attack in 1*1 and 2*1 knights and 1*4 and 2*4 number index attack in 1*2 and 2*2 knights
we set 2*6 chessboard 8 knights because of 1*3 and 2*3 number index attack in 1*1 and 2*1 knights and 1*4 and 2*4 number index attack in 1*2 and 2*2 knights
we set 2*7 chessboard 8 knights because of 1*3 and 2*3 number index attack in 1*1 and 2*1 knights and 1*4 and 2*4 number index attack in 1*2 and 2*2 knights and 1*7 and 2*7
number index attack in 1*5 and 2*5 knights
we set 2*8 chessboard 8 knights because of 1*3 and 2*3 number index attack in 1*1 and 2*1 knights and 1*4 and 2*4 number index attack in 1*2 and 2*2 knights and1*7 and 2*7 number index attack in 1*5 and 2*5 knights and 1*8 and 2*8 number index attack in 1*6 and 2*6 knights.
for any m==2|| n==2
our ans will be :
mx=max(n,m);
ans=mx;
if(mx%4==1||mx%4==3)ans++;
if(mx%4==2)
ans+=2;
Problem Link https://lightoj.com/problem/knights-in-chessboard
Solution in C++:
///La ilaha illellahu muhammadur rasulullah
///******Bismillahir-Rahmanir-Rahim******///
///Abul Hasnat Tonmoy
///Department of CSE,23rd batch
///Islamic University,Bangladesh
///**********ALLAH IS ALMIGHTY************///
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
for(int i=1; i<=t; i++)
{
int m,n;
cin>>m>>n;
if(m==1||n==1)
printf("Case %d: %d\n",i,max(n,m));
else if(m==2||n==2)
{
int mx=max(n,m);
int ans=mx;
if(mx%4==1||mx%4==3)ans++;
else if(mx%2==2)
ans+=2;
printf("Case %d: %d\n",i,ans);
}
else
printf("Case %d: %d\n",i,(n*m+1)/2);
}
}
No comments