题目描述
N*M网格中有^、v、<、>四种字符,分别表示上下左右,可以任选一个格子作为起点,每一步必须朝向格子标注移动到下一个格子,走出网格边界立即结束,最多可以经过多少个不同的格子?
输入描述:
第一行两个正整数N、M
下面N行,每行M个字符表示方向
输出描述:
可能经过的不同格子的数量
样例
2 3
^v<
>>^
5
2 3
vvv
<<<
4
(BFS) $O(n^2)$
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 2010;
int h[N], e[N], ne[N], idx;
int q[N];
int n, m, ans = 0;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int BFS(int u) {
int hh = 0, tt = 0;
q[0] = u;
vector<int> d(N, -1);
d[u] = 1;
while (hh <= tt) {
auto t = q[hh++];
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (d[j] == -1) {
d[j] = d[t] + 1;
q[++tt] = j;
}
}
}
return *max_element(d.begin(), d.end());
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
char c; cin >> c;
if (c == '^' && i > 0) add(i * m + j, (i - 1) * m + j);
else if (c == 'v' && i < n - 1) add(i * m + j, (i + 1) * m + j);
else if (c == '<' && j > 0) add(i * m + j, i * m + j - 1);
else if (c == '>' && j < m - 1) add(i * m + j, i * m + j + 1);
}
}
for (int i = 0; i < n * m - 1; i++) {
ans = max(ans, BFS(i));
}
cout << ans << endl;
return 0;
}
(DFS) $O(n^2)$
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2010;
int h[N], e[N], ne[N], idx;
bool st[N];
int n, m, ans = 0;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int DFS(int u) {
st[u] = true;
int cnt = 1;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) {
cnt += DFS(j);
}
}
return cnt;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
char c; cin >> c;
if (c == '^' && i > 0) add(i * m + j, (i - 1) * m + j);
else if (c == 'v' && i < n - 1) add(i * m + j, (i + 1) * m + j);
else if (c == '<' && j > 0) add(i * m + j, i * m + j - 1);
else if (c == '>' && j < m - 1) add(i * m + j, i * m + j + 1);
}
}
for (int i = 0; i < n * m - 1; i++) {
memset(st, false, sizeof st);
ans = max(ans, DFS(i));
}
cout << ans << endl;
return 0;
}