I-Penguins

链接：https://ac.nowcoder.com/acm/contest/11253/I

做法：最多可能状态只有20的4次方，即16w，所以直接bfs就行

需要注意的点是：当一边碰到障碍或边界，是不会移动的，所以可能只有一侧移动

#include
using namespace std;
bool vis[22][22][22][22];
bool a[25][25];
bool b[25][25];
char c[25][25];
char d[25][25];string ans;struct ZT{int x1,y1;int x2,y2;string road;
};
struct XD{int dx;int dy;string move;
}mv[4];
void init(){mv[0].dx=0;mv[0].dy=1;mv[0].move="R";mv[1].dx=0;mv[1].dy=-1;mv[1].move="L";mv[2].dx=-1;mv[2].dy=0;mv[2].move="U";mv[3].dx=1;mv[3].dy=0;mv[3].move="D";}
bool checkl(int x,int y){if(a[x][y])return 0;return 1;
}
bool checkr(int x,int y){if(b[x][y])return 0;return 1;
}
bool bounder(int x,int y){if(x>=1&&x<=20&&y>=1&&y<=20)return 1;return 0;
}void pro(){int x1=20,y1=20,x2=20,y2=1;for(int i=0;i<ans.length();i++){c[x1][y1]='A';d[x2][y2]='A';if(ans[i]=='L'){if(checkl(x1,y1-1)&&bounder(x1,y1-1)){y1=y1-1;}if(checkr(x2,y2+1)&&bounder(x2,y2+1)){y2=y2+1;}}if(ans[i]=='R'){if(checkl(x1,y1+1)&&bounder(x1,y1+1)){y1=y1+1;}if(checkr(x2,y2-1)&&bounder(x2,y2-1)){y2=y2-1;}}if(ans[i]=='U'){if(checkl(x1-1,y1)&&bounder(x1-1,y1)){x1=x1-1;}if(checkr(x2-1,y2)&&bounder(x2-1,y2)){x2=x2-1;}}if(ans[i]=='D'){if(checkl(x1+1,y1)&&bounder(x1+1,y1)){x1=x1+1;}if(checkr(x2+1,y2)&&bounder(x2+1,y2)){x2=x2+1;}}}c[x1][y1]='A';d[x2][y2]='A';
}int main(){init();string tmp;for(int i=1;i<=20;i++){cin>>tmp;for(int j=1;j<=20;j++){if(tmp[j-1]=='.') a[i][j]=0;else if(tmp[j-1]=='#') a[i][j]=1;c[i][j]=tmp[j-1];}cin>>tmp;for(int j=1;j<=20;j++){if(tmp[j-1]=='.') b[i][j]=0;else if(tmp[j-1]=='#') b[i][j]=1;d[i][j]=tmp[j-1];}}bool flag=1;ZT s;s.x1=20,s.y1=20,s.x2=20,s.y2=1,s.road="";queue<ZT>q;q.push(s);vis[20][20][20][1]=1;while(flag){ZT tmp=q.front();q.pop();for(int i=0;i<4;i++){int x1,y1,x2,y2;x1=tmp.x1+mv[i].dx;y1=tmp.y1+mv[i].dy;string rd=tmp.road+mv[i].move;if(i<2){x2=tmp.x2+mv[!i].dx;y2=tmp.y2+mv[!i].dy;}else{x2=tmp.x2+mv[i].dx;y2=tmp.y2+mv[i].dy;}if(!checkl(x1,y1)||!bounder(x1,y1)){x1=tmp.x1;y1=tmp.y1;}if(!checkr(x2,y2)||!bounder(x2,y2)){x2=tmp.x2;y2=tmp.y2;}if(!vis[x1][y1][x2][y2]){vis[x1][y1][x2][y2]=1;ZT nzt;nzt.x1=x1;nzt.x2=x2;nzt.y1=y1;nzt.y2=y2;nzt.road=rd;q.push(nzt);if(nzt.x1==1&&nzt.x2==1&&nzt.y1==20&&nzt.y2==1){ans=nzt.road;flag=0;}}}}cout<<ans.size()<<endl<<ans<<endl;pro();for(int i=1;i<=20;i++){for(int j=1;j<=20;j++){cout<<c[i][j];}cout<<" ";for(int j=1;j<=20;j++){cout<<d[i][j];}cout<<endl;}//system("pause");return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！