题目描述
森林中有两只奶牛,约翰想要捕获它们。
整个森林可以看作是一个 $10×10$ 的平面方格图。
每个方格可以有四种表示方式:
.
,表示这个方格是空地。8
,表示这个方格是障碍物。F
,表示这个方格上站着农夫约翰。C
,表示这个方格上站着那两头牛。
注意,约翰和奶牛可以走到空地格子中,但是不能走到障碍物格子中,当两者相遇时,表示约翰抓到了奶牛。
下面是一个网格示例:
*...*.....
......*...
...*...*..
..........
...*.F....
*.....*...
...*......
..C......*
...*.*....
.*.*......
奶牛会以固定的方式在地图中徘徊。
每分钟,奶牛可以做出一个动作,向前方移动一个格子,或顺时针转向 $90$ 度。
当奶牛的前方没有障碍物且不会走出地图时,它们会选择向前移动一个方格。
否则,它们会选择顺时针转向 $90$ 度。
约翰的移动方式与奶牛完全相同。
如果,两者在移动的过程中,彼此掠过,则认为它们没有相遇。
如果在某一分钟结束时,两者都停留在了同一个方格内,则认为两者相遇,约翰抓住了牛。
现在,给定你方格图,以及两者的初始位置,请判断经过多少分钟后,约翰能抓住牛。
假设,两者的初始朝向都是向北(地图方向为上北下南左西右东)。
如果不能抓住牛,则输出 $0$。
输入格式
共 $10$ 行,每行包含 $10$ 个字符,表示完整的森林地图。
保证地图中,只出现一个 $C$ 和一个 $F$。
输出格式
输出一个整数,表示约翰抓住牛花费的时间。
如果抓不住牛,则输出 $0$。
输入样例
*...*.....
......*...
...*...*..
..........
...*.F....
*.....*...
...*......
..C......*
...*.*....
.*.*......
输出样例
49
解法一:DFS
DFS 解法是自己直观上想出来的。
但是我怀疑 y 总的数据太弱了,但应该不可能递归到 $160000$ 层…,好叭,试了一下,果真可以。
C++ 代码
#include <iostream>
using namespace std;
const int N = 12;
int n = 10, xf, yf, xc, yc, ans;
string mp[N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int f = 0, c = 0;
bool flag = false, suce = false;
bool check(int x, int y)
{
return x >= 0 && x < n && y >= 0 && y < n;
}
void dfs(int xf, int yf, int xc, int yc)
{
if (flag) {
return ;
}
if (xf == xc && yf == yc) {
flag = true;
return ;
}
if (ans > 160000) {
flag = true;
suce = true;
return ;
}
++ans;
int x1, y1, x2, y2;
// 走人
x1 = xf + dx[f], y1 = yf + dy[f];
if (!check(x1, y1) || mp[x1][y1] == '*') {
f = (f + 1) % 4;
x1 = xf, y1 = yf;
}
// 走牛
x2 = xc + dx[c], y2 = yc + dy[c];
if (!check(x2, y2) || mp[x2][y2] == '*') {
c = (c + 1) % 4;
x2 = xc, y2 = yc;
}
dfs(x1, y1, x2, y2);
}
int main()
{
for (int i = 0; i < n; ++i) {
cin >> mp[i];
for (int j = 0; j < mp[i].size(); ++j) {
if (mp[i][j] == 'F') xf = i, yf = j;
if (mp[i][j] == 'C') xc = i, yc = j;
}
}
// 直走、顺时针旋转 90 度
dfs(xf, yf, xc, yc);
if (suce) {
cout << 0 << endl;
}
else {
cout << ans << endl;
}
return 0;
}
解法二:模拟
其实两类解法的思想是一样的。
我来解释两个关键点。
1、方位的判断:先确定一个方位用变量表示,之后按照北东南西顺时针方向来走。
2、状态的判断:10 x 10 的网格每一个坐标点有北东南西四个状态,总共的状态数量就是 400 x 400。
然后在 400 * 400 的状态中去枚举即可。
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 12;
int n = 10, xf, yf, xc, yc;
string mp[N];
int df = 0, dc = 0;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void move(int& x, int& y, int& d)
{
int xs = x + dx[d], ys = y + dy[d];
if (xs < 0 || xs >= n || ys < 0 || ys >= n || mp[xs][ys] == '*') {
d = (d + 1) % 4;
}
else {
x = xs, y = ys;
}
}
int main()
{
for (int i = 0; i < n; ++i) {
cin >> mp[i];
for (int j = 0; j < n; ++j) {
if (mp[i][j] == 'F') xf = i, yf = j;
if (mp[i][j] == 'C') xc = i, yc = j;
}
}
// 400 * 400 = 160000 种状态
for (int i = 0; i <= 200; ++i) {
if (xf == xc && yf == yc) {
cout << i << endl;
return 0;
}
move(xf, yf, df);
move(xc, yc, dc);
}
cout << 0 << endl;
return 0;
}