9517 Link Link Look

该题有题解

时间限制:2000MS 内存限制:65535K
提交次数:67 通过次数:18

题型: 编程题语言: G++;GCC

Description

相信大家都玩过连连看.连看看是在一个方格上面有各种不同的图案,没图案的格子视为通道.如果能找到两个图案,他们之间能通过通道而转弯次数不超过2的道路连接起来,那么这两个图案视为可消图案

例如

10024

02057

33001

这样两个1,2,3都可消

但

10030

04070

06000

54321

这样的两个1是不可消的,但如果把3消去,两个1就可以消去了..

由于规则太复杂了,导致玩的时候我有点混乱,所以想请你帮我.现在我在一个局面卡住了,进行不下去.所以想请你帮我看看现在还有多少对可以消去的图案(注意不一定所有的图案都配对的)

例如

10024

02057

33001

就有3对

输入格式

第一行是两个数n,m表示方格大小为n*m (50>n,m>0)

接下来是n行,每一行有m个数,0表示空,其余数字表示对应的图案,图案数字类型不超过20

输出格式

输出一个数字表示当前局面可消对数(我可以有多少种选择)

看样例2

输入样例

Sample Input #1:

3 5

1 0 0 2 4

0 2 0 5 7

3 3 0 0 1

Sample Input #2:

1 4

1 1 1 1

输出样例

Sample Output #1:

Sample Output #2:

提示

方格四周是没东西的,连线不能超过方格,一超过就不知道去到什么异空间了(@_@)

注意Sample Input/Output用#1和#2。。。，并不是输入的部分，而是表示这是两组不同的数据。

即，你所需做的是读入一组数据，输出答案，然后就可以结束程序了。

来源

ick2

作者

a470086609

这题的解题思路就是用深度优先搜索。用个for将每个不为0的点都进行dfs，并且将每个dfs过的点用数组flag存储起来，防止遍历后面的点进行dfs时重复计数了这个地方。而在对一个起始点进行dfs前还要用到一个book数组，用来将dfs时能够与起始点进行消对的点i用book[i]标记好，防止起始点向别的方向搜索时如果回到这个点上而又重复计数。再具体的解释在代码注释中。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,m,sum=0;

int map[55][55],flag[55][55],book[55][55],next[4][2]= {{0,1},{1,0},{0,-1},{-1,0}}; //next表示移动的四个方向

//flag用来标记已经消过的点，避免重复计数。book用来当前搜索中已走过的路，避免重走

//

void dfs(int x,int y,int change,int dect,int ans)//change表示已转弯次数，dect为上一次移动时的方向

{

    int tx,ty;

    for(int i=0; i<4; i++) //枚举四个移动方向

    {

        tx=x+next[i][0];

        ty=y+next[i][1];

        if(tx>=n||tx<0||ty>=m||ty<0)

            continue;

        if(!map[tx][ty])//如果是通路

        {

                if(change<2)

                {

                    if(dect!=i)

                        dfs(tx,ty,change+1,i,ans);

                    else dfs(tx,ty,change,i,ans);

                }

                else if(change==2)

                {

                    if(dect!=i)

                        continue;

                    else dfs(tx,ty,change,i,ans);

                }

        }

        if(map[tx][ty]==ans)//如果找到了相同数字

        {

            if(!flag[tx][ty])//如果是未曾标记过的

            {

                if(!book[tx][ty])//如果是未曾消过的

                {

                    if(change==2&&i!=dect)

                        continue;

                    else

                    {

                        book[tx][ty]=1;

                        sum++;

                    }

                }

            }

        }

    }

}

int main()

{

    int i,j;

    memset(map,0,sizeof(map));

    memset(book,0,sizeof(book));

    memset(flag,0,sizeof(flag));

    scanf("%d%d",&n,&m);

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

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

            scanf("%d",&map[i][j]);

    //

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

    {

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

        {

            if(map[i][j]!=0)

            {

                flag[i][j]=1;

                dfs(i,j,-1,-1,map[i][j]);//因为刚开始在起始点时是没有原始方向的(在dfs函数里用i等

                //于0 1 2 3来表示四个方向，故这里起始用为-1，在第一次进入dfs时从0开始枚举，同时转弯次数

                //也会从-1变为0。

                memset(book,0,sizeof(book));//这里记得要重新清0

            }

        }

    }

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

    return 0;

}

巴特西

9517 Link Link Look

9517 Link Link Look

Description

输入格式

输出格式

输入样例

输出样例

提示

来源

作者

最新文章

热门文章