杭电7:Smzzl with Greedy Snake
题面:在XoY平面内,有只贪吃蛇,蛇头每次旋转90度和前进一单位,都会花费一单位时间,现连续出现n个食物,求花最少时间吃完的步骤。
解析:模拟题,注意细节,每次吃一个食物,蛇头的方向和坐标就要发生改变,一开始一看到贪吃蛇就想到bfs,就交给队友写了。队员nb
代码:
#include<bits/stdc++.h> using namespace std; int t,x,y,d,n,p,q; int main(){ std::ios::sync_with_stdio(false); scanf("%d",&t); while(t--){ scanf("%d%d%d",&x,&y,&d); scanf("%d",&n); while(n--){ scanf("%d%d",&p,&q); int dx=p-x,dy=q-y; if(d==0){ if(dx>0){ if(dy>0){ while(dy--) cout<<"f"; cout<<"c"; while(dx--) cout<<"f"; d=1; } else{ dy=-dy; cout<<"c"; while(dx--) cout<<"f"; cout<<"c"; while(dy--) cout<<"f"; d=2; } } else{ dx=-dx; if(dy>0){ while(dy--) cout<<"f"; cout<<"u"; while(dx--) cout<<"f"; d=3; } else{ dy=-dy; cout<<"u"; while(dx--) cout<<"f"; cout<<"u"; while(dy--) cout<<"f"; d=2; } } } else if(d==1){ if(dx>0){ if(dy>0){ while(dx--) cout<<"f"; cout<<"u"; while(dy--) cout<<"f"; d=0; } else{ dy=-dy; while(dx--) cout<<"f"; cout<<"c"; while(dy--) cout<<"f"; d=2; } } else{ dx=-dx; if(dy>0){ cout<<"u"; while(dy--) cout<<"f"; cout<<"u"; while(dx--) cout<<"f"; d=3; } else{ dy=-dy; cout<<"c"; while(dy--) cout<<"f"; cout<<"c"; while(dx--) cout<<"f"; d=3; } } } else if(d==2){ if(dx>0){ if(dy>0){ cout<<"u"; while(dx--) cout<<"f"; cout<<"u"; while(dy--) cout<<"f"; d=0; } else{ dy=-dy; while(dy--) cout<<"f"; cout<<"u"; while(dx--) cout<<"f"; d=1; } } else{ dx=-dx; if(dy>0){ cout<<"c"; while(dx--) cout<<"f"; cout<<"c"; while(dy--) cout<<"f"; d=0; } else{ dy=-dy; while(dy--) cout<<"f"; cout<<"c"; while(dx--) cout<<"f"; d=3; } } } else if(d==3){ if(dx>0){ if(dy>0){ cout<<"c"; while(dy--) cout<<"f"; cout<<"c"; while(dx--) cout<<"f"; d=1; } else{ dy=-dy; cout<<"u"; while(dy--) cout<<"f"; cout<<"u"; while(dx--) cout<<"f"; d=1; } } else{ dx=-dx; if(dy>0){ while(dx--) cout<<"f"; cout<<"c"; while(dy--) cout<<"f"; d=0; } else{ dy=-dy; while(dx--) cout<<"f"; cout<<"u"; while(dy--) cout<<"f"; d=2; } } } x=p,y=q; } cout<<endl; } }