题意:就是Y和M在@相遇的最短的时间。
思路:基本的广搜题,先Y搜一次,然后M搜一次,最后求出Y和M在@相遇的最短的时间。
代码实现:
#include#include #include using namespace std;int n,m,count1[210][210],count2[210][210],visited[210][210];//count1记录的是Y到各个点的最短的时间int b[4][2]={ { 1,0},{-1,0},{ 0,1},{ 0,-1}};//count2记录的是M到各个点最短的时间char str[210][210];struct node{ int x; int y;};int nima(int x,int y){ if(x>=0&&x =0&&y q; p.x=x;p.y=y; q.push(p); if(flag==1) { while(!q.empty())//基本的广搜,此时我用的是队列,此前我用的一直是数组,还是队列好多了 { p=q.front(); q.pop(); for(int i=0;i<4;i++) { t1=p.x+b[i][0];t2=p.y+b[i][1]; if(nima(t1,t2)) { visited[t1][t2]=-1; temp.x=t1; temp.y=t2; q.push(temp); count1[t1][t2]=count1[p.x][p.y]+11; } } } } else { while(!q.empty()) { p=q.front(); q.pop(); for(int i=0;i<4;i++) { t1=p.x+b[i][0];t2=p.y+b[i][1]; if(nima(t1,t2)) { visited[t1][t2]=-1; temp.x=t1; temp.y=t2; q.push(temp); count2[t1][t2]=count2[p.x][p.y]+11; } } } }}int main(){ int i,j,x1,y1,x2,y2,a[40005][2],num,flag,min; while(scanf("%d%d",&n,&m)!=EOF) { getchar(); num=0;min=100000000; for(i=0;i (count1[a[i][0]][a[i][1]]+count2[a[i][0]][a[i][1]])) min=count1[a[i][0]][a[i][1]]+count2[a[i][0]][a[i][1]]; } } printf("%d\n",min); } return 0;}