「JoyOI1234」bench与奔驰
背景 Background
公园里有个人在练开奔驰 – -!，但是总是撞在bench上 (众人曰：狼来了，快跑啊!)
描述 Description
公园里的bench与奔驰都是无敌的，不会被撞坏。
由于开奔驰的人比较”有特点”，总是向上下左右四个方向开，而且只会在撞到椅子之后改变方向(起步时除外) – -!
现在他给你一张地图，上面标明 他的位置 、 公园里的bench的位置 和 他想到达的位置，可能会有冲出地图的可能
请你告诉他最少撞多少下才能到达目的地，并答应事成之后会给你一辆奔驰……………………………………….的照片
输入格式 InputFormat
第一行，两个数，分别表示地图的行和列，都不大于50
以下是地图，”.”表示地面，”S”表示起点，”E”表示终点,”B”表示bench(什么意思呢？)
保证只有一个终点和一个起点，并不会出现其他字符
输出格式 OutputFormat
第一行，表示他能不能到达目的地。如果能，就输出”Yes”。否则，输出”No”
如果能到达目的地，就在第二行输出最少的撞击次数
数据范围和注释 Hint
测试数据1：点火后直接向右走
测试数据2：四个方向都会冲出地图
来源 Source
某个经典的游戏……
题解
被学弟问的傻逼题逗了
在撞上椅子之前就会拐弯。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,m,bx,by,ex,ey; int xx[5]={-1,1,0,0},yy[5]={0,0,1,-1}; int mp[55][55]; int vis[55][55][5]; char ch[55]; struct data{int x,y,s,dir;}q[100005]; bool bfs() { int t=0,w=0,nowx,nowy; if(bx==ex&&by==ey){printf("Yes\n0");return 1;} q[w].x=bx;q[w].y=by;q[w].dir=0;vis[bx][by][0]=1;w++; q[w].x=bx;q[w].y=by;q[w].dir=1;vis[bx][by][1]=1;w++; q[w].x=bx;q[w].y=by;q[w].dir=2;vis[bx][by][2]=1;w++; q[w].x=bx;q[w].y=by;q[w].dir=3;vis[bx][by][3]=1;w++; while(t<w) { int x=q[t].x,y=q[t].y,step=q[t].s,dir=q[t].dir;t++; nowx=x;nowy=y; while(1) { nowx=nowx+xx[dir],nowy=nowy+yy[dir]; if(nowx<1||nowy<1||nowx>n||nowy>m||mp[nowx][nowy]||vis[nowx][nowy][dir])break; vis[nowx][nowy][dir]=1; if(mp[nowx+xx[dir]][nowy+yy[dir]]) { for(int k=0;k<4;k++) { if(vis[nowx][nowy][k])continue; vis[nowx][nowy][k]=1; q[w].x=nowx;q[w].y=nowy;q[w].dir=k; q[w].s=step+1; w++; if(nowx==ex&&nowy==ey){printf("Yes\n%d",step);return 1;} } break; } if(nowx==ex&&nowy==ey) {printf("Yes\n%d",step);return 1;} } } return 0; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%s",ch); for(int j=1;j<=m;j++) { if(ch[j-1]=='B')mp[i][j]=1; else if(ch[j-1]=='S'){bx=i;by=j;} else if(ch[j-1]=='E'){ex=i;ey=j;} } } if(!bfs())printf("No"); return 0; } |
计数器 9296190
OI 课件=>
OI 课件=>
orz 黄学长，我不是故意问你题目逗你的