#########
Sample Output 37 5 517 17 9
虽然都说水题,但是真的感觉左遍历和右遍历的时候处理起来很复杂,代码也显得十分冗长。
#include <stdio.h> #include <string.h> int next[4][2]={{0,-1},{-1,0},{0,1},{1,0}},book[50][50];// int u=1,d=3,r=2,l=0,min=9999999;// 主要是方向的建立比较重要 char map[50][50]; struct node{//一开始打算将四个方向都标记出来,其实只需要正前方一个方向转向就好了 int f; int h; int r; int l; }dir; struct nodx{ int x; int y; }s,e; struct kk{ int x,y,step; }que[100100],qc,qu; int head,end; int m,n; void bfs() { int i,j; while (head<end){ qc=que[head]; for (i=0;i<4;i++){ int x=next[i][0]+qc.x,y=next[i][1]+qc.y; if (x<0||y<0||x>=m||y>=n) continue; if (!book[x][y]&&map[x][y]!='#'){ book[x][y]=1; que[end].x=x; que[end].y=y; que[end].step=que[head].step+1; if (x==e.x&&y==e.y){ min=que[end].step; return ; } end++; } } head++; } } int main () { int t,i; scanf ("%d",&t); while(t--){ scanf ("%d%d",&m,&n); i=m;m=n;n=i; getchar (); int step_r=1,step_l=1,j; for (i=0;i<m;i++){ for (j=0;j<n;j++){ scanf ("%c",&map[i][j]); if (map[i][j]=='S'){ s.x=i;s.y=j; if (j==0) dir.f=r; if (j==n-1) dir.f=l; if (i==0) dir.f=d; if (i==m-1) dir.f=u; head=0;end=1; que[head].x=i;que[head].y=j;que[head].step=1; } if (map[i][j]=='E'){ e.x=i;e.y=j; } //printf ("%d %d\n",i,j); } getchar(); } bfs();//最短只能用广搜,DFS将TLE。 int x=s.x,y=s.y,d=dir.f; while (x!=e.x||y!=e.y){ int tt=0; d--;//左遍历的时候要先往左转一次 if (d==-1) d=3; if ((x+next[d][0]>=0&&x+next[d][0]<m&&y+next[d][1]>=0&&y+next[d][1]<n)&&map[x+next[d][0]][y+next[d][1]]!='#'){ x+=next[d][0];y+=next[d][1]; step_l++; // printf ("%d-%d\n",x,y); }//左转能走就走更新坐标 else{//左转一次不能移动就开始右转 while (1){ d++; tt++; if (d==4) d=0; if (x+next[d][0]<0&&x+next[d][0]>=m&&y+next[d][1]<0&&y+next[d][1]>=n) continue; if (map[x+next[d][0]][y+next[d][1]]!='#'){ x+=next[d][0];y+=next[d][1]; step_l++; // printf ("%d-%d\n",x,y); break; } if (tt==3) break; } } } x=s.x;y=s.y;d=dir.f; while (x!=e.x||y!=e.y){ int tt=0; d++;//右遍历同理右转一次 if (d==4) d=0; if ((x+next[d][0]>=0&&x+next[d][0]<m&&y+next[d][1]>=0&&y+next[d][1]<n)&&map[x+next[d][0]][y+next[d][1]]!='#'){ x+=next[d][0];y+=next[d][1]; step_r++; // printf ("%d-%d\n",x,y); }//右转能走就走,更新坐标 else{//右转一次不能移动就开始左转。 while (1){ d--; tt++; if (d==-1) d=3; if (x+next[d][0]<0&&x+next[d][0]>=m&&y+next[d][1]<0&&y+next[d][1]>=n) continue; if (map[x+next[d][0]][y+next[d][1]]!='#'){ x+=next[d][0];y+=next[d][1]; step_r++; // printf ("%d-%d\n",x,y); break; } if (tt==3) break; } } } printf ("%d %d %d\n",step_l,step_r,min); memset(book,0,sizeof(book)); memset(map,0,sizeof(map)); memset(que,0,sizeof(que)); min=999999;step_l=1;step_r=1; } return 0; }以上代码很多地方是不必要的比如min=9999999是之前用深搜超时后没有改正过来。
下面贴一个别人的左右遍历的方法
int Depth_FirstSearch(int x1,int y1,int d,int x2,int y2) { int new_x,new_y,i,count=1; if(x1==x2&&y1==y2) return count; d=(d+3)%4; i=d; for(i=d;i<d+4;i++) { new_x=x1+dir[i%4][0]; new_y=x2+dir[i%4][1]; if(new_x>=0&&new_x<h&&new_y>=0&&new_y<w&&maze[new_x][new_y]!='#') { count++; d=i;//记录当前方向 Depth_FirstSearch(new_x,new_y,d,x2,y2); } } }形参依次是起始坐标,方向,结束坐标。d=(d+3)%4;代表左转90°。所以这个函数只能实现左遍历。然而-.-
count1=Depth_FirstSearch(start_x,start_y,0,end_x,end_y); //左遍历 count2=Depth_FirstSearch(end_x,end_y,0,start_x,start_y);//右遍历右遍历正好等于终点到起点的左遍历。。。利用这个规律便极大的优化了代码量。