poj 3050 Hopscotch 穷举

缘起

日常浪费生命 poj 3050 Hopscotch

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
给定一个5*5的地图，每个格子上有一个数字。从一个格子出发（上下左右4个方向），走5步将数字连起来可以构造出
一个6位数。问该地图可以构造出多少个不同的6位数。

【输入】
5*5的数字矩阵

【输出】
数字种类

【样例输入】
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

【样例输出】
15

【提示】
OUTPUT DETAILS: 
111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 
121212, 211111, 211121, 212111, and 212121 can be constructed. No other values are 
possible.

【限制】
Time limit 1000 ms
Memory limit 65536 kB

【来源】
USACO 2005 November Bronze

dfs即可.

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
//#include "stdafx.h"

#include <stdio.h>
#include <set>
using namespace std;
//#define LOCAL

set<int> s;
int a[5][5], nxt[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

void dfs(int i, int j, int step, int num) // step是迄今已经走了几步, num是迄今凑成的数, (i,j)是现在要走的步数
{
	if (step == 6)
	{
		s.insert(num);
		return;
	}
	num = num*10+a[i][j]; //洪特规则
	for (int k = 0,ni,nj; k<4; k++)
	{
		ni = i+nxt[k][0], nj = j+nxt[k][1];
		if (~ni&&ni<5&&~nj&&nj<5)
		{
			dfs(ni,nj,step+1,num);
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	for (int i = 0; i<5;i++)
	{
		for (int j = 0; j<5; j++)
		{
			scanf("%d", a[i]+j);
		}
	}
	for (int i = 0; i<5; i++)
	{
		for (int j = 0; j<5; j++)
		{
			dfs(i,j,0,0);
		}
	}
	printf("%d\n", s.size());
	return 0;
}

ac情况

Status Accepted
Time 79ms
Memory 444kB
Length 795
Lang C++
Submitted 2019-08-24 07:15:31
Shared
RemoteRunId 20794039