AcWing 1111. 字母
原题链接
简单
作者:
王小强
,
2021-01-18 18:49:10
,
所有人可见
,
阅读 356
DFS + Backtracking
// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;
const int N = 25;
char grid[N][N];
int m, n;
vector<int> seen(26);
static constexpr int dirs[] { 0, -1, 0, 1, 0 };
int dfs(int x, int y) {
if (x < 0 || y < 0 || x == n || y == m || seen[grid[y][x] - 'A'])
return 0;
seen[grid[y][x] - 'A'] = 1;
int steps = 0;
for (int i = 0; i < 4; ++i)
steps = max(steps, dfs(x + dirs[i], y + dirs[i + 1]));
seen[grid[y][x] - 'A'] = 0; // backtracking ...
return 1 + steps;
}
int main() {
cin >> m >> n;
for (int y = 0; y < m; ++y)
for (int x = 0; x < n; ++x) cin >> grid[y][x];
seen.clear();
cout << dfs(0, 0);
return 0;
}