网站 设计 精髓,电子商务网站建设的主要内容,合肥网络优化推广公司,简易网站模板[USACO2.4] 两只塔姆沃斯牛 The Tamworth Two
题目描述
两只牛逃跑到了森林里。Farmer John 开始用他的专家技术追捕这两头牛。你的任务是模拟他们的行为#xff08;牛和 John#xff09;。
追击在 10 10 10 \times 10 1010 的平面网格内进行。一个格子可以是#xff1…[USACO2.4] 两只塔姆沃斯牛 The Tamworth Two
题目描述
两只牛逃跑到了森林里。Farmer John 开始用他的专家技术追捕这两头牛。你的任务是模拟他们的行为牛和 John。
追击在 10 × 10 10 \times 10 10×10 的平面网格内进行。一个格子可以是一个障碍物两头牛它们总在一起或者 Farmer John。两头牛和 Farmer John 可以在同一个格子内当他们相遇时但是他们都不能进入有障碍的格子。
一个格子可以是
. 空地* 障碍物C 两头牛F Farmer John。
这里有一个地图的例子
*...*.....
......*...
...*...*..
..........
...*.F....
*.....*...
...*......
..C......*
...*.*....
.*.*......牛在地图里以固定的方式游荡。每分钟它们可以向前移动或是转弯。如果前方无障碍地图边沿也是障碍它们会按照原来的方向前进一步。否则它们会用这一分钟顺时针转 90 度。 同时它们不会离开地图。
Farmer John 深知牛的移动方法他也这么移动。
每次每分钟Farmer John 和两头牛的移动是同时的。如果他们在移动的时候穿过对方但是没有在同一格相遇我们不认为他们相遇了。当他们在某分钟末在某格子相遇那么追捕结束。
读入十行表示地图。每行都只包含 10 个字符表示的含义和上面所说的相同。保证地图中只有一个 F 和一个 C。F 和 C 一开始不会处于同一个格子中。
计算 Farmer John 需要多少分钟来抓住他的牛假设牛和 Farmer John 一开始的行动方向都是正北即上。 如果 John 和牛永远不会相遇输出 0。
输入格式
输入共十行每行 10 个字符表示如上文描述的地图。
输出格式
输出一个数字表示 John 需要多少时间才能抓住牛们。如果 John 无法抓住牛则输出 0。
样例 #1
样例输入 #1
*...*.....
......*...
...*...*..
..........
...*.F....
*.....*...
...*......
..C......*
...*.*....
.*.*......样例输出 #1
49提示
翻译来自NOCOW
USACO 2.4 思路
在每次移动时先判断是否超出边界或者遇到障碍物如果是则改变方向否则更新位置。
用一个六维数组 vis 来记录某时刻牛和农民的坐标和方向如果发现牛和农民在同一坐标和同一方向重复出现则说明陷入死循环农民和牛永远不会相遇输出 0。
如果牛和农民同一时刻在同一坐标则相遇输出消耗的时间。 AC代码
#include iostream
#include cstring
#define AUTHOR HEX9CF
using namespace std;const int N 10;const int dirs[4][2] {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};struct S
{int x, y;int dir;
} cow, fm;char a[N][N];
bool vis[N][N][N][N][4][4];void move(S obj)
{int tx obj.x dirs[obj.dir][0];int ty obj.y dirs[obj.dir][1];if (tx 9 || ty 9 || tx 0 || ty 0 || * a[tx][ty]){if (obj.dir 3){obj.dir 0;}else{obj.dir;}}else{obj.x tx;obj.y ty;}
}void dfs(int x)
{if (cow.x fm.x cow.y fm.y){cout x endl;return;}move(cow);move(fm);if (vis[cow.x][cow.y][fm.x][fm.y][cow.dir][fm.dir]){cout 0 endl;return;}vis[cow.x][cow.y][fm.x][fm.y][cow.dir][fm.dir] 1;dfs(x 1);
}int main()
{memset(vis, 0, sizeof(vis));for (int i 0; i 10; i){for (int j 0; j 10; j){cin a[i][j];if (C a[i][j]){cow.x i;cow.y j;cow.dir 0;}if (F a[i][j]){fm.x i;fm.y j;fm.dir 0;}}}dfs(0);return 0;
}
