Agent J problem no:1037 (Lightoj)

This problem is a bitmask DP problem & very much interesting  :)   .......


#include<bits/stdc++.h>
using namespace std;
#define maxx 15*1000000+3
int _N,dp[(1<<15)+9],health[16],arra[16][16];

/*dp[] array may need maximum index,this index is such a number that
is in binary 15 digit of which bit are set (111111111111111) in decimal 2^15*/

char s[16];

//-------------Set ,reset, check function-------------

int Set(int N,int pos)
{
    return N=N| (1<<pos);
}

int reset(int N,int pos)
{
    return N=N& ~(1<<pos);
}

bool check(int N,int pos)
{
    return (bool)  (N & (1<<pos));
}

//--------------------bitmask function---------------

int bitmask(int mask)
{
    if(mask==(1<<_N)-1)    return 0;
    if(dp[mask]!=-1)      return dp[mask];
    int mnshot=maxx;
    for(int i=0;i<_N;i++)
    {
        if(check(mask,i)==0)    //agent is searching for a live one to shoot
        {
            int mn=health[i];   //max value is if agent shoot everyone by KM 0.45
            for(int j=0;j<_N;j++)
            {
                if(check(mask,j)==1) // searching deads to get weapon
                {
                    int ans=ceil( (double)health[i] / (double)(arra[j][i]) );
                    //minimize number of shoots to kill this alive man with dead's weapon
                    mn=min(mn,ans);
                }
            }
            int shot=mn+bitmask(Set(mask,i));//declaring i as dead and continue next operation
            mnshot=min(mnshot,shot);
        }
    }
    return dp[mask]=mnshot;
}

//----------------main function---------------------

int main()
{
    int T;
    scanf("%d",&T);
    for(int tt=1;tt<=T;tt++)
    {
        memset(dp,-1,sizeof(dp));

        //----------------taking input

        scanf("%d",&_N);
        for(int nn=0;nn<_N;nn++)
        {
            scanf("%d",&health[nn]);
        }
        getchar();
        for(int i=0;i<_N;i++)
        {
            gets(s);
            for(int j=0;j<_N;j++)
            {
                arra[i][j]=s[j]-48;
                if(arra[i][j]==0)
                    arra[i][j]=1;   //to remove 0 value from matrix nor minimized value would be 0
            }
        }


        int n=0;
        // in bit sequence 0 is live,1 is dead(that can supply agent a weapon)

        int mnshot=maxx;
        for(int i=0;i<_N;i++)
        {
            int shot=health[i]+bitmask(Set(n,i));//make this man dead by Set bit to 1
            mnshot=min(mnshot,shot);
        }

        printf("Case %d: %d\n",tt,mnshot);
    }
    return 0;

}