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

dalao都用模拟做，蒟蒻用的是BFS........ 还加了些优化 详见代码注释： ```cpp #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; } ```