Hopscotch(POJ-3050)

題目：

The cows play the child’s game of hopscotch in a non-traditional way. Instead of a linear set of numbered boxes into which to hop, the cows create a 5x5 rectilinear grid of digits parallel to the x and y axes They then adroitly hop onto any digit in the grid and hop forward, backward, right, or left (never diagonally) to another digit in the grid. They hop again (same rules) to a digit

(potentially a digit already visited).

With a total of five intra-grid hops, their hops create a six-digit integer (which might have leading zeroes like 000201).

Determine the count of the number of distinct integers that can be created in this manner.

Input

* Lines 1…5: The grid, five integers per line

Output

* Line 1: The number of distinct integers that can be constructed

Sample Input

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 2 1
1 1 1 1 1
           

Sample Output

解題思路：深搜的題目，分别從5^5的矩陣各個頂點上下左右出發，然後走六步組成一個六位數，判斷能組成多少個不同的六位數

注意：每組成一個六位數就要标記一下，是以數組至少要開七位。

程式代碼：

#include<stdio.h>
#include<string.h>
int n=0;
int a[15][15],book[15][15],f[10000010];//因為要組成六位數，是以數組至少要開七位
int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
void dfs(int x,int y,int t,int sum)
{
	int i,j,k,tx,ty;
	if(t==5)
	{
		if(f[sum]==0)
			n++;
		f[sum]=1;
		return;
	}
	for(k=0;k<=3;k++)
	{
		tx=x+next[k][0];
		ty=y+next[k][1];
		if(tx<1||tx>5||ty<1||ty>5)
			continue;
		dfs(tx,ty,t+1,sum*10+a[tx][ty]);
	}
	return;
}
int main()
{
	int i,j,k,t,sum;
	for(i=1;i<=5;i++)
		for(j=1;j<=5;j++)
			scanf("%d",&a[i][j]);
	for(i=1;i<=5;i++)
		for(j=1;j<=5;j++)
			dfs(i,j,0,a[i][j]);
	printf("%d\n",n);
	return 0;		
}