曾彪彪的个人网站
首页
文章列表
>>
文章详情
# P1518 [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two (理解多维数组)
作者:
曾彪彪
日期:
2025-07-01 08:02:30
阅读(37)
分类:
Algorithm
# P1518 [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two (理解多维数组) ## 题目描述 两只牛逃跑到了森林里。Farmer John 开始用他的专家技术追捕这两头牛。你的任务是模拟他们的行为(牛和 John)。 追击在 $10 \times 10$ 的平面网格内进行。一个格子可以是:一个障碍物,两头牛(它们总在一起),或者 Farmer John。两头牛和 Farmer John 可以在同一个格子内(当他们相遇时),但是他们都不能进入有障碍的格子。 一个格子可以是: - `.` 空地; - `*` 障碍物; - `C` 两头牛; - `F` Farmer John。 这里有一个地图的例子: ```plain *...*..... ......*... ...*...*.. .......... ...*.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 这是一道模拟题,模拟部分不难,难在怎样判断永远不会相遇,之前的想法是,如果牛和John在某一时刻,重复出现在某个坐标,并且方向还相同,比如在t100时刻,牛出现在2,3坐标,John出现在7,8坐标,在9999时刻,牛又出现在2,3坐标,John出现在7,8坐标,并且方向都是向北,那么可以判定为死循环,无法相遇。 但是不知道怎样实现这个功能,于是上网搜索了一下,发现可以使用6维数组来实现,但是我不理解为什么要使用六维数组,于是继续搜索多维数组的概念和用法,最终理解: - 多维数组,在存储上,其实是线性结构的嵌套,比如二维数组int a[3][3],是三个一维数组a[3],那么三维数组int a[3][3][3],是有三个二维数组a[3][3].结构如下: ``` c++ int a[3]={1,2,3}; // 线性结构 int a[3][3]={ //二维数组结构 {1,2,3}, //多个线性结构 {1,2,3}, {1,2,3} } int a[3][3][3]= //三维数组结构 { { //多个二维数组结构 {1,2,3}, {1,2,3}, {1,2,3} }, { {1,2,3}, {1,2,3}, {1,2,3} }, { {1,2,3}, {1,2,3}, {1,2,3} } } ``` - 在逻辑上,多维数组表示几个因素可以唯一确定一个值,比如一位数组,一个因素就可以确定一个值。比如一个列表存储了身份证号码,那么一个身份证号码就可以唯一确定一个值。二维数组,比如一张图片,一对{x,y}可以唯一确定一个像素点。 对于三维数组,比如我们购买的电影票,上面有播放大厅hall,作为排row和作为号seat,那么这三个因素就可以唯一确定一个座位号,可以使用三维数组来存储。如果再加上 播放场次,如上午场,下午场,就可以通过4个因素来唯一确定一个值,就可以使用4维数组进行存储。 那么对于上面的题目,就可以通过f的x,y,以及方向,以及c的x,y,以及方向来唯一确定John和牛的状态,如果这个状态重复出现过,那么可以判为死循环。 理解了这一点,做题就清晰了。附上AC代码: ```c++ /** start time: 14:42 End time: Type: simulator Solution: - the key point is how to validate John can't catch up the cow. - Use a six dimensional array to store the location status, if the status duplicated, then return 0 - - test case: - *...*..... ......*... ...*...*.. .......... ...*.F.... *.....*... ...*...... ..C......* ...*.*.... .*.*...... - - *...*..... C.....*... ...*...*.. .F........ ...*...... *.....*... ...*...... .........* ...*.*.... .*.*...... - *.C..*..... ......*... ...*...*.. .......... ********** *.....*... ...*...... .........* ...*.*.... .*.*...F... first submit score: 100 cause: **/ #include <bits/stdc++.h> using namespace std; vector<int> dx = {0, 1, 0, -1}; // direction of x, from east, south, weat to north vector<int> dy = {1, 0, -1, 0}; const int n = 10; int fx, fy, fd = 3, cx, cy, cd = 3; vector<vector<char>> grid(10, vector<char>(10)); int visited[n][n][4][n][n][4] = {0}; void move(int &x, int &y, int &d) { int tx = x + dx[d]; int ty = y + dy[d]; if (tx < 0 || tx >= n || ty < 0 || ty >= n || grid[tx][ty] == '*') { d = (d + 1) % 4; return; } x = tx; y = ty; } void chase() { int steps = 0; while (true) { if (visited[fx][fy][fd][cx][cy][cd] == 1) { cout << 0 << endl; break; } if (fx == cx && fy == cy) { cout << steps << endl; break; } visited[fx][fy][fd][cx][cy][cd] = 1; move(fx, fy, fd); move(cx, cy, cd); steps++; } } int main() { // freopen("C:/Users/zengsam/Downloads/P1042_2.in", "r", stdin); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> grid[i][j]; if (grid[i][j] == 'C') { cx = i; cy = j; } if (grid[i][j] == 'F') { fx = i; fy = j; } } } chase(); return 0; } ```
评论(0)
评论(必填)
名称(必填)
联系方式(可选)
验证码(必填)
提交
评论(必填)
名称(必填)
联系方式(可选)
验证码(必填)