本文最后更新于 718 天前,其中的信息可能已经有所发展或是发生改变。
Original Link
思想:
DFS
。
- 由题意易知,从左上角的字母开始搜索,最多经过 26 个不同的字母。
- 则将走过的字母利用
vis
数组进行标记,若走过标记为 True
。
- 递归处理每一个格子,每一层利用偏移量数组遍历上下左右四个方向。
- 用
res
维护最大可以走过的不同字母的个数,每次更新,当 res == 26
时达到最大,可以提前返回。
- 注意起始搜索的字母也需要标记。
代码:
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| const int N = 100; |
| |
| int n, m, res; |
| |
| char mp[N][N]; |
| |
| bool vis[N * 3]; |
| |
| int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1}; |
| |
| void dfs(int x, int y, int cnt){ |
| res = max(res, cnt); |
| if(res == 26) return; |
| for(int i = 0; i < 4; i ++){ |
| int l = x + dx[i], r = y + dy[i]; |
| if(l >= 0 && l < n && r >= 0 && r < m && !vis[mp[l][r]]){ |
| vis[mp[l][r]] = 1; |
| dfs(l, r, cnt + 1); |
| vis[mp[l][r]] = 0; |
| } |
| } |
| } |
| |
| void solve(){ |
| cin >> n >> m; |
| for(int i = 0; i < n; i ++) cin >> mp[i]; |
| vis[mp[0][0]] = 1; |
| dfs(0, 0, 1); |
| cout << res << endl; |
| } |
| |
| int main(){ |
| solve(); |
| return 0; |
| } |