题目大意：有Y和M两个人要去kfc也就是@吃饭，问最短路是多少
思路：dfs和bfs应该都可以 需要走所有的点，开一个time数组计算两个人到@的时间之和，最后求最小的就可以了
不过我当时一看最短就直接上bfs了
#include<stdio.h> #include<string.h> char map[205][205];//存储地图 int time[205][205];//存储时间 int n,m; int min=0; int x1,y3,x2,y2; int book[205][205]; int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};//四个方向 void bfs(int a,int b); int check(int a,int b){//判断可不可以走 if(a>=0&&a<n&&b>=0&&b<m&&book[a][b]==0&&map[a][b]!='#'){ return 1; } return 0; } int main(void){ while(scanf("%d%d",&n,&m)!=EOF){ int i,j; memset(time,0,sizeof(time));//初始化 min=999999; getchar(); for(i=0;i<n;i++){ gets(map[i]); for(j=0;j<m;j++){ if(map[i][j]=='Y'){ x1=i;y3=j; } if(map[i][j]=='M'){ x2=i;y2=j; } } } bfs(x1,y3);//bfs两个点 bfs(x2,y2); for(i=0;i<n;i++){ for(j=0;j<m;j++){ if(map[i][j]=='@'&&time[i][j]!=0){ min=min>time[i][j]?time[i][j]:min;//求最短时间 } } } printf("%d\n",min*11); } return 0; } void bfs(int a,int b){ memset(book,0,sizeof(book)); book[a][b]=1; struct node{ int x; int y; int step; }q[50000]; int head=0; int tail=1; q[head].x=a; q[head].y=b; q[head].step=0; while(head<tail){ time[q[head].x][q[head].y]+=q[head].step;//把时间加到time数组中 其实time就相当于step int i; for(i=0;i<4;i++){ int tx=q[head].x+dir[i][0]; int ty=q[head].y+dir[i][1]; if(check(tx,ty)){ q[tail].x=tx; q[tail].y=ty; q[tail].step=q[head].step+1; tail++; book[tx][ty]=1; } } head++; } }
