[数据结构与算法]洛谷P1518 [USACO2.4]两只塔姆沃斯牛

题目链接

很有意思的一道模拟题,之前其实看过挺多次的,都因为没思路或者觉得难写没动.今天静下心仔细研究下,总算是A掉了.

这道题我遇到的坑点还是不少的,如果完全靠自己做结果应该是个未知数,

1. 之前影响我对这道题难度判断的地方就是边界检查和无解判断.边界检查这个多做点题还是有经验了的,就是把地图开大点,地图边界算作障碍物,就可以省去比较繁琐的越界检查.即便如此我还是因为少开了一行一列而被迫debug.无解判断偷摸看了题解,有哈希和数组两种判断法,我开了个三维数组来作判断.农夫在同一个方向进入同一格的次数过多,将被判断为无解.然后我因为这个次数开的太少wa了两个点再次被迫花5秒debug
2. 写代码的时候横纵坐标没打注释,把自己整不会了,样例输出的答案少了3.判断出问题还是蛮快的,但改代码因为没写注释懵逼了半天.本来以为要对结构动刀,仔细捋明白之后改了个方向就成了…

#include <bits/stdc++.h>
using namespace std;

const int N = 10;

char m[12][12];//存地图
int movex[4] = {-1,0,1,0};//x轴移动方向上的值,顺序为北东南西
int movey[4] = {0,1,0,-1};//y轴移动方向上的值
pair<int,int> f,c;//农民和牛的坐标
int fm,cm;//农民和牛的方向,默认向北
int flag[4][12][12];//判断无解,如果多次在同一方向移动到同一位置,则直接跳出程序
int ans;//答案

int main()
{
    memset(m,'*',sizeof m);//初始化地图全是障碍物
    for(int i = 1 ; i <= N ; i++)
        for(int j = 1 ; j <= N ; j++)
        {
            cin >> m[i][j];
            if(m[i][j] == 'F')//存农民
                f = make_pair(i,j);
            else if(m[i][j] == 'C')//存牛
                c = make_pair(i,j);
        }
    
    while(1)//死循环,有答案才给跳出
    {
        ans++;//首先加时间
        //农民部分
        if(m[f.first + movex[fm]][f.second + movey[fm]] != '*')//前方不是障碍物,就向前移动
        {
            f.first += movex[fm];
            f.second += movey[fm];
            flag[fm][f.first][f.second]++;//判断值+1
        }
        else//否则转向
            fm = (fm + 1) % 4;
        //牛部分,思路同上
        if(m[c.first + movex[cm]][c.second + movey[cm]] != '*')
        {
            c.first += movex[cm];
            c.second += movey[cm];
        }
        else
            cm = (cm + 1) % 4;
        if(f == c)//两边都移动完之后判断是否相遇
        {
            cout << ans;
            break;
        }
        if(flag[fm][f.first][f.second] > 50)//如果在同一个地方打转的次数太久,就无解
        {
            cout << 0;
            break;
        }
    }
    
    return 0;
}