题解 P1518 【两只塔姆沃斯牛 The Tamworth Two】

2018-07-06 16:22:17


dalao都用模拟做,蒟蒻用的是BFS........

还加了些优化

详见代码注释:

#include <bits/stdc++.h>
using namespace std;
#define NDEBUG //蒟蒻调试用
int sx,sy,ex,ey,dy[] = {0,1,0,-1},dx[] = {-1,0,1,0};
//方向,对应北东南西。北相当于x坐标-1
const int N = 10;
char a[N][N];
struct Node{int sx,sy,ex,ey,sh,eh,cnt;}; 
//sx,sy,sh:FJ信息 ex,ey,eh:COW信息 cnt步数
size_t toHash(int a,int b,int c,int d,int e,int f)
{
    return a + b * 100ll + c * 10000ll + d * 1000000ll + e * 100000000ll 
            + f * 10000000000ll;//哈希值
}
struct Pos{int x,y,h;};//相当于STL的tuple,存储方位信息
set<size_t> vis;//判重
queue<Node> q;//BFS必备
Pos nwPos(int x,int y,int h) //扩展用函数
{
    int nx = x + dx[h],ny = y + dy[h];
    if (nx < 0 || ny < 0 || nx >= N || ny >= N || a[nx][ny] == '*')
        return {x,y,(h + 1) % 4};
    return {nx,ny,h}; //根据当前方向和位置获取新的方向,位置
}
int main ()
{
    for (int i = 0;i < 10;i++) scanf("%s",a[i]);
    for (int i = 0;i < 10;i++)
        for (int j = 0;j < 10;j++)
            if (a[i][j] == 'F') sx = i,sy = j;
            else if (a[i][j] == 'C') ex = i,ey = j;
            //存储FJ,cow坐标
#ifndef NDEBUG //调试代码
    cout << sx << ' ' << sy << ' ' << ex << ' ' << ey << '\n';
#endif
    q.push({sx,sy,ex,ey,0,0,0});vis.insert(toHash(sx,sy,ex,ey,0,0));//初始朝北,方位代码(偏移量dx,dy数组下标)为0
    while (!q.empty())
    {
        Node nd = q.front();q.pop();
        if (nd.sx == nd.ex && nd.sy == nd.ey) 
        {
            printf("%d",nd.cnt);
            return 0;//结束
        } 
        auto x = nwPos(nd.sx,nd.sy,nd.sh);//扩展
        auto y = nwPos(nd.ex,nd.ey,nd.eh);
        auto hashNum = toHash(x.x,x.y,y.x,y.y,x.h,y.h);
        //得到哈希值(auto是C++11新特性)
        if (vis.count(hashNum)) continue;
        vis.insert(hashNum);//判重
        q.push({x.x,x.y,y.x,y.y,x.h,y.h,nd.cnt + 1});
        //入队
    }
    printf("0"); //无法抓到牛
    return 0;
}