DFS3

发表于 | 更新于: | 次
字数统计: 515 字 | 阅读时长 ≈ 2 分钟

没歌了，上一个老婆(Hibiki)角色曲吧，顺带庆祝我的生日↓

没错我又来水博客了(逃

还是模板题(大概)

给出一个roe × col 的大写字母矩阵，一开始的位置为左上角，你可以向上下左右四个方向移动，并且不能移向曾经经过的字母。问最多可以经过几个字母。

[输入]

第一行，输入字母矩阵行数RR和列数SS，1≤R,S≤201≤R,S≤20。

接着输出RR行SS列字母矩阵。

[输出]

最多能走过的不同字母的个数。

[输入样例]

1
2
3
4
5
> 3 6
> HFDFFB
> AJHGDH
> DGAGEH
>

[输出样例]

1
2
> 6
>

我这题居然卡了一个小时，可见我有多菜Orz

贴代码

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<bits/stdc++.h>
#define FOR(x,k,z) for(register int x = k; x <= z; x++)
#define FFOR(x,k,z) for(register int x = k; x < z; x++)
typedef long long int64;

using namespace std;

int r, s, tot = 1;
bool usedc[27];
char maps[25][25];
bool used[25][25];
int block[4][2] = { {-1, 0},{1, 0} ,{0, -1}, {0, 1} };//上下左右，四联通

int dfs(int x, int y, int step)
{
	if (tot < step)
	{
		tot = step;
	}
	FOR(i, 0, 4)
	{
		int xx = x + block[i][0];//求四联通坐标
		int yy = y + block[i][1];
		if (xx >= 1 && xx <= r && yy >= 1 && yy <= s && used[xx][yy] == false && usedc[maps[xx][yy] - 'A'] == false)//注意边界处理和是否曾经抵达过，字母是否抵达过
		{
			used[xx][yy] = true;
			usedc[maps[xx][yy] - 'A'] = true;
			dfs(xx, yy, step + 1);//我一开始用的是++step，被卡了好久
			used[xx][yy] = false;//回溯，毕竟这题没说不能回头
			usedc[maps[xx][yy] - 'A'] = false;
		}
	}
	return 0;
}

int main()
{
	cin >> r >> s;
	FOR(i, 1, r)
	{
		FOR(j, 1, s)
		{
			cin >> maps[i][j];
		}
	}
	usedc[maps[1][1] - 'A'] = true;//标记起点字母
	used[1][1] = true;//标记起点抵达状况
	dfs(1, 1, 1);
	cout << tot;
	return 0;
}

看来我还是太菜了，不到1=就女装的flag怕是要回收了…