[CSP-J 2024 T2] 地图探险
第一种方法,模拟算法。
#include <bits/stdc++.h>
using namespace std;
#define N 1010
int T;
int n, m, k;
int x, y, d;
int fx[] = {0, 1, 0, -1};
int fy[] = {1, 0, -1, 0};
bool v[N][N];
char maze[N][N];
char tmp[N];
int adventure();
int main()
{
cin >> T;
while (T--)
{
cin >> n >> m >> k;
cin >> x >> y >> d;
for (int i = 1; i <= n; i++)
{
cin >> tmp;
for (int j = 0; j <= m; j++)
maze[i][j + 1] = tmp[j];
}
cout << adventure() << endl;
}
return 0;
}
int adventure()
{
int cnt = 0;
memset(v, false, sizeof(v));
v[x][y] = true;
while (k--)
{
int dx = x + fx[d];
int dy = y + fy[d];
if (dx >= 1 && dx <= n && dy >= 1 && dy <= m && maze[dx][dy] == '.')
{
x = dx;
y = dy;
}
else
d = (d + 1) % 4;
v[x][y] = true;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (v[i][j])
cnt++;
return cnt;
}这道题很容易想到深度优先搜索算法,但是地图太大用深搜只能获得部分分。
