12510 - Collecting Coins

[ioi]

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MM 30

char matrix[MM][MM];
int vis[MM][MM];
int ret,row,col;

int inx[4]={0,-1,0,1};  //right,up,left,down
int iny[4]={1,0,-1,0};

void set()
{
    memset(matrix,0,sizeof(matrix));
    memset(vis,0,sizeof(vis));
}

void dfs(int x,int y)
{
    int i,j,k;
    for(k=0;k<4;k++)
    {
        i=x+inx[k];
        j=y+iny[k];
        if(i>=0 && i<row && j>=0 && j<col && matrix[i][j]=='X' && !vis[i][j])
        {
            vis[i][j]=1;

        }
        else if(i>=0 && i<row && j>=0 && j<col && matrix[i][j]=='O' && !vis[i][j])
        {
            if(k==0)
            {
                if(matrix[i][j+1]=='.' && i>=0 && i<row && j+1>=0 && j+1<col && !vis[i][j+1])
                {
                    matrix[i][j]='.';
                    matrix[i][j+1]='O';
                    vis[i][j]=1;
                    dfs(i,j);
                }

            }
            else if(k==1)
            {
                if(matrix[i-1][j]=='.' && i-1>=0 && i-1<row && j>=0 && j<col && !vis[i-1][j])
                {
                    matrix[i][j]='.';
                    matrix[i-1][j]='O';
                    vis[i][j]=1;
                    dfs(i,j);
                }

            }
            else if(k==2)
            {
                if(matrix[i][j-1]=='.' && i>=0 && i<row && j-1>=0 && j-1<col && !vis[i][j-1])
                {
                    matrix[i][j]='.';
                    matrix[i][j-1]='O';
                    vis[i][j]=1;
                    dfs(i,j);
                }

            }
            else if(k==3)
            {
                if(matrix[i+1][j]=='.' && i+1>=0 && i+1<row && j>=0 && j<col && !vis[i+1][j])
                {
                    matrix[i][j]='.';
                    matrix[i+1][j]='O';
                    vis[i][j]=1;
                    dfs(i,j);
                }

            }
        }
        else if(i>=0 && i<row && j>=0 && j<col && matrix[i][j]=='C' && !vis[i][j])
        {
            ret++;
            matrix[i][j]='.';
            vis[i][j]=1;
            dfs(i,j);
        }
        else if(i>=0 && i<row && j>=0 && j<col && matrix[i][j]=='.' && !vis[i][j])
        {
            vis[i][j]=1;
            dfs(i,j);
        }
    }
}

int main()
{
    int test,t;
    int i,j,flag;
    scanf("%d",&test);
    for(t=0;t<test;t++)
    {
        scanf("%d%d",&row,&col);
        set();
        for(i=0;i<row;i++)
        {
            scanf("%s",matrix[i]);
        }
        flag=0;
        for(i=0;i<row;i++)
        {
            for(j=0;j<col;j++)
            {
                if(matrix[i][j]=='S')
                {
                    ret=0;
                    flag=1;
                    matrix[i][j]='.';
                    vis[i][j]=1;
                    dfs(i,j);
                    break;
                }
            }
            if(flag) break;
        }
        printf("%d\n",ret);
    }
    return 0;
}

WA pls help me out....thanks
sory for posting different volume because of absence of CXXV

[brianfry713]

Input reposted from http://ideone.com/pCm7M0

Code: Select all

1
4 7
S.XX..X
..XC.CX
...XOOC
.......

AC output 2