首页 > 代码库 > 【学校集训】【USACO15DecG】Bessie's Dream
【学校集训】【USACO15DecG】Bessie's Dream
点此进入原题
（注：上面的参考译文是有问题的，等一下会在题解中说明）
算法：最短路或搜索(BFS)
题解：
本题用最短路可以做，但是构图比较麻烦，搜索要相对简单一点。
搜索需要四个量表示状态：(x,y)坐标，一个bool型变量表示是否有橘子味，还有一个量来表示方向（处理紫色方块时要用）
对于当前状态，如果前一个状态所在坐标代表紫色瓷砖并且可以继续滑行（按原方向下一个坐标所代表的不是粉红色或蓝色瓷砖），那么你就要继续按照原方向滑行。
否则就枚举4个方向然后按照相应情况判断是否有橘子味，之后就是朴素的BFS了～
重要：本题的读题坑
1. 在紫色瓷砖上滑行一次也要步数+1，即使滑到的下一个仍然是紫色瓷砖。
在参考译文中写的“一次滑行无论通过多少瓷砖只算一次移动”显然是不对的，因为原文是"Sliding through a tile counts as a move"，即滑行一个瓷砖算一次移动，而不是无论多少瓷砖。这句话本身好像也通不过去啊……
2. 在初始状态(1,1)的步数应该是0
在老师讲题的时候说(1,1)的步数应该是1，老师给的AC代码貌似初始步数也是1，但是我写的AC代码初始步数是0，并且如果初始步数是1的话那么对于第4个测试点会有矛盾。推算原题的意思应该也是初始步数为0.不过对于老师的代码能AC我还是表示十分惊奇的
后来发现老师的代码里好像有ans-1?好玄学啊
下面是代码时间：
#include<cstdio>#include<cstring>#include<queue>#include<algorithm>using namespace std;const int N=1005;int n,m,a[N][N];int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};struct Node{ int x,y,d; bool orange; };queue<Node> q;int step[N][N][5][3];bool check(Node f){ int x=dx[f.d]+f.x,y=dy[f.d]+f.y; return a[x][y]!=0&&a[x][y]!=3;}int main(){ freopen("dream.in","r",stdin); freopen("dream.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); memset(step,-1,sizeof(step)); step[1][1][0][0]=step[1][1][2][0]=0; //初始步数为0 q.push((Node){1,1,0,false}); //方向为向下或向右 q.push((Node){1,1,2,false}); while(!q.empty()) { Node f=q.front(); q.pop(); for(int i=0;i<4;i++) { int x=f.x+dx[i],y=f.y+dy[i]; if(x<1||y<1||x>n||y>m||a[x][y]==0) continue; if(!f.orange&&a[x][y]==3) continue; if(a[f.x][f.y]==4&&check(f)) //处理前一个是4的情况(我直接放在循环内部了) { if(i!=f.d) continue; //方向要相同 bool o; if(a[x][y]==2) o=true; else o=false; if(step[x][y][i][o]==-1) { step[x][y][i][o]=step[f.x][f.y][i][f.orange]+1; //滑行步数要+1 q.push((Node){x,y,i,o}); } } else { bool o; if(a[x][y]==2) o=1; else if(a[x][y]==4) o=0; else o=f.orange; if(step[x][y][i][o]!=-1) continue; step[x][y][i][o]=step[f.x][f.y][f.d][f.orange]+1; q.push((Node){x,y,i,o}); } } } int ans=1<<30; for(int i=0;i<4;i++) for(int j=0;j<=1;j++) if(step[n][m][i][j]!=-1) ans=min(ans,step[n][m][i][j]); printf("%d",ans==1<<30?-1:ans);}
这个代码在USACO上是能AC的，但是自测会TLE。解决办法是手写队列。然而我懒得手写了QWQ
彩蛋：贴代码的时候发现倒数第三行写的是max QAQ，或许数据中只有一条合法路径？（惊恐
【学校集训】【USACO15DecG】Bessie's Dream
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。