UVA 11953 - Battleships(cpp file)

Problem Type : Graph(DFS)



#include<stdio.h>
#include<string.h>
#define MAX 106
long n,m,coun=0,color[MAX][MAX];
char mat[MAX][MAX];
int X[4]={-1,0,0,1};
int Y[4]={0,-1,1,0};
void dfs(int i,int j)
{
    color[i][j]=1;
    int k,vx,vy;
    for(k=0;k<4;k++)
    {
        vx=X[k]+i;
        vy=Y[k]+j;
        if(vx>=0 && vx<n && vy>=0 && vy<n && (mat[vx][vy]=='x'||mat[vx][vy]=='@'))
        {
            if(color[vx][vy]==0)
            {
                dfs(vx,vy);
            }
        }
    }
}
int main()
{
    int test,i,j,cas=0;
    scanf("%d",&test);
    while(test--)
    {
        cas++;
        scanf("%d",&n);
       memset(mat,'\0',sizeof(mat));
        for(i=0; i<n; i++)
        {
            for(j=0; j<n; j++)
            {
               scanf(" %c",&mat[i][j]);
            }
        }
        memset(color,0,sizeof(color));
         coun=0;
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                if(mat[i][j]=='x' && color[i][j]==0)
                {
                    coun++;
                    dfs(i,j);

                }
            }
        }
        printf("Case %d: %d\n",cas,coun);
    }

}