POJ 3050: Hopscotch_hopscotch算法详解

思路：
1、遍历网格中的所有点，以遍历到的点为起点进行深度优先搜索，深度优先搜索递归6次后返回
2、用set来存储所得到的数，以达到去重的目的

#include <cstdio>
#include <cstring>
#include <stack>
#include <queue> 
#include <algorithm> 
#include<iostream>
#include<map>
#include<set>
using namespace std;
#define MAX_A 10000
int grid[5][5];
//方向数组，用于遍历四个方向 
int xd[4] = {0,1,0,-1};
int yd[4] = {1,0,-1,0};
set<int> numset;
//深度优先搜索，每个起点都重复一次，到达6次时返回 
//用set记录组合
//参数分别为数、数的位数、牛当前的坐标 
void dfs(int number,int digit,int x,int y){
	number = number*10+grid[x][y];
	digit++;
	if(digit==6){
		numset.insert(number);
		return;
	}else{
		//遍历四个方向,递归 
		for(int i=0;i<4;i++){
			int xi = x+xd[i];
			int yi = y+yd[i];
			if(xi>=0&&xi<5&&yi>=0&&yi<5){
				dfs(number,digit,xi,yi);
			}			
		} 
		
	}
} 

void solve(){
	for(int i=0;i<5;i++){
		for(int j=0;j<5;j++){
			dfs(0,0,i,j);
		}
	}
}

int main(){
	//输入 
	for(int i=0;i<5;i++){
		for(int j=0;j<5;j++){
			scanf("%d",&grid[i][j]);
		}
		getchar();
	}
	
	solve();
	printf("%d\n",numset.size());
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58