poj 3050 Hopscotch

2024-01-08 06:38

文章标签 poj hopscotch 3050

本文主要是介绍poj 3050 Hopscotch，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给你一个5x5的方格，你可以在任意点开始，走5步（上下左右4个方向，可以往回走，和迷宫不一样），把你走的每个方格上的数字按你走方格的顺序排列好（共6个数字，起始点也有一个），求有多少种不同的排列方式。

思路：把每一个点dfs一遍，求总数，其中6个数字的排列可以转化成一个6位数，储存在一个数组里（我用amount[100000]存的），N代表有多少中可能。

#include<stdio.h>

int map[5][5];
int mov[][2]={{-1,0},{0,1},{1,0},{0,-1}};
int amount[100000];
int N=0;
void dfs(int x,int y,int step,int num)// num代表走过的数字按顺序排列起来得到的整数
{
           int i,x1,y1,flag;
           if(step==6)
           {
               flag=0;
                for(i=0;i<N;i++)
                {

                   if(num==amount[i])
                    {
                           flag=1;
                           break;
                    }
                }

            if(!flag)
           {
                 amount[N]=num;
                  N++;
           }
           return ;
            }
            for(i=0;i<4;i++)
           {
                     x1=x+mov[i][0];
                     y1=y+mov[i][1];
                     if(x1<0||x1>=5||y1<0||y1>=5||vis[x1][y1])
                                continue;

                    dfs(x1,y1,step+1,num*10+map[x1][y1]);   //num*10+map[x1][y1]就是把排列转化成数字

             }
return ;
}
int main(void)
{
           int i,j;
            for(i=0;i<5;i++)
                   for(j=0;j<5;j++)
                      scanf("%d",&map[i][j]);
           for(i=0;i<5;i++)         //穷举每一个位置可以走的方案
                  for(j=0;j<5;j++)
                 {
                          memset(vis,0,sizeof(vis));
                          dfs(i,j,1,map[i][j]);
                 }
     printf("%d\n",N);
}