最少拐弯数

-

输入

4 4
S..*
.*.*
....
.*.T

输出

2

-
题意：给你一个有起点与终点的图，求最小拐弯数。
-
BFS，往一个方向一直走（即同一方向一次全入队）。
注意遇已走过处应选择不更新（没必要），同时跳过继续走，而非停止脚步。

#include<cstdio>
#include<queue>
using namespace std;
int n,m;
char a[2017][2017];
int step[2017][2017];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
struct S{
    int x,y;
}be,en;
 
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i)for(int j=0;j<m;++j)step[i][j]=-1;
    getchar();
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            scanf("%c",&a[i][j]);
            if(a[i][j]=='S')be.x=i,be.y=j;
            if(a[i][j]=='T')en.x=i,en.y=j;
        }
        getchar();
    }
    
    queue<S> q;
    q.push(be);
    while(!q.empty()){
        S head=q.front(),now;   q.pop();
         
        for(int i=0;i<4;++i){
            now.x=head.x+dx[i],now.y=head.y+dy[i];
             
            while(now.x>=0&&now.y>=0&&now.x<n&&now.y<m&&a[now.x][now.y]!='*'){
               
                if(step[now.x][now.y]==-1){ //没有走过
                    step[now.x][now.y]=step[head.x][head.y]+1;
                    q.push(now);
                }
                 
                if(now.x==en.x&&now.y==en.y){printf("%d\n",step[now.x][now.y]);return   0;}
                 
                now.x+=dx[i],now.y+=dy[i];
            }
        }
    }

    printf("troil\n");
    return  0;
}

-
加了一个记录已走过方向的dir，优化后

#include<cstdio>
#include<queue>
using namespace std;
int n,m;
char a[2017][2017];
int step[2017][2017];
int dx[]={0,1,0,-1,233};
int dy[]={1,0,-1,0,233};
struct S{
	int x,y,dir;
	//若需要初始化，以下
	//S(){}	//无参 
	//S(int xx,int yy):x(xx),y(yy){}	//两个int参数 
	
}be,en;

int main(){
//	S s;
//	S S2(1,2);
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;++i)for(int j=0;j<m;++j)step[i][j]=-1;
	getchar();
	for(int i=0;i<n;++i){
		for(int j=0;j<m;++j){
			scanf("%c",&a[i][j]);
			if(a[i][j]=='S')be.x=i,be.y=j,be.dir=233;
			if(a[i][j]=='T')en.x=i,en.y=j;
		}
		getchar();
	}
	
	queue<S> q;
	q.push(be);
	while(!q.empty()){
		S head=q.front(),now;	q.pop();
		
		for(int i=0;i<4;++i){
			now.x=head.x+dx[i];
			now.y=head.y+dy[i];
			if(i==0||i==2)now.dir=0;
			else	now.dir=1;
			if(now.dir==head.dir)	continue;	//优化
			while(now.x>=0&&now.y>=0&&now.x<n&&now.y<m&&a[now.x][now.y]!='*'){
				
				if(step[now.x][now.y]==-1){	//没有走过 
					step[now.x][now.y]=step[head.x][head.y]+1;
					q.push(now);
				}
				
				if(now.x==en.x&&now.y==en.y){printf("%d\n",step[now.x][now.y]);return	0;}
				
				now.x+=dx[i],now.y+=dy[i];
			}
		}
	}

	printf("troil\n");
	return	0;
}