hdu5319 简单模拟

题意很好懂，大致就是三种颜色，红和蓝一起会变绿，给个终态矩阵，问从原始状态到终态最少画几笔？按一定规则画

思路就是记红为1，蓝为2，绿为3，先遍历绿色，针对每一块绿色进行删除，每找到一块绿色，首先将它置零，然后主对角线上和它挨着的红色或绿色-1，副对角线上和它挨着的蓝色或绿色-2，ans+2；知道所有绿色遍历完为止。然后在遍历剩余的红色和蓝色，红色块主对角线上和它挨着的红色-1（包括它）ans+1，绿色副对角线上和它挨着的蓝色-2（包括它）ans+1。最后输出ans即可。

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

int n,m;

int g[][];

int ans=;

void dfs_1(int x,int y)  //左上

{

    while(g[x][y]==||g[x][y]==)

    {

     //   puts("1");

        g[x][y]--;

        x--;

        y--;

    }

}

void dfs_2(int x,int y)  // 右下

{

    while(g[x][y]==||g[x][y]==)

    {

    //    puts("1");

        g[x][y]--;

        x++;

        y++;

    }

}

void dfs_3(int x,int y)  // 左下

{

    while(g[x][y]==||g[x][y]==)

    {

     //   puts("1");

        g[x][y]-=;

        x++;

        y--;

    }

}

void dfs_4(int x,int y)  // 右上

{

    while(g[x][y]==||g[x][y]==)

    {

    //    puts("1");

        g[x][y]-=;

        x--;

        y++;

    }

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        ans=;

        memset(g,,sizeof(g));

        scanf("%d",&n);

        for(int i=;i<=n;i++)

        {

            char cc[];

            memset(cc,'\0',sizeof(cc));

            scanf("%s",cc);

            m=strlen(cc);

            for(int j=;j<m;j++)

            {

                if(cc[j]=='R') g[i][j+]=;

                if(cc[j]=='B') g[i][j+]=;

                if(cc[j]=='G') g[i][j+]=;

            }

        }

        for(int a=;a<=n;a++)

        {

            for(int b=;b<=m;b++)

            {

                if(g[a][b]==)

                {

                    g[a][b]=;

                    dfs_1(a-,b-);

                    dfs_2(a+,b+);

                    dfs_3(a+,b-);

                    dfs_4(a-,b+);

                    ans+=;

                }

            }

        }

        for(int c=;c<=n;c++)

        {

            for(int d=;d<=m;d++)

            {

                if(g[c][d]==)

                {

                    g[c][d]=;

                    dfs_1(c-,d-);

                    dfs_2(c+,d+);

                    ans++;

                }

                else if(g[c][d]==)

                {

                    g[c][d]=;

                    dfs_3(c+,d-);

                    dfs_4(c-,d+);

                    ans++;

                }

            }

        }

        printf("%d\n",ans);

    }

}

巴特西

hdu5319 简单模拟

最新文章

热门文章