codeforces 793B - Igor and his way to work(dfs、bfs)

题目链接：http://codeforces.com/problemset/problem/793/B

题目大意：告诉你起点和终点，要求你在只能转弯两次的情况下能不能到达终点。能就输出“YES”，不能就输出“NO”。

解题思路：这算是经典的转弯题了，接近半年没写搜索题了，，所以今天先拿这道题开刀吧。这个题关键就是“判重”，如何记录走过的点。我们可以开个三维数组，记录各个坐标各个方向上的转弯数，如果下次在到这个点这个方向，那就比较转弯数，如果这次转弯数大于等于已经记录的转弯数那就不用再找下去了，因为这次能走到的地方，上次肯定也能走到。估计一下时间复杂度大概为O(4*3n)。

dfs:

 #include<iostream>

 #include<cstring>

 using namespace std;

 const int N=1e3+;

 int m,n;

 bool flag=false;

 char map[N][N];

 int vis[N][N][];//*关键*用来标记走过的点，记录该点朝着各方向转弯数

 int d[][]={{,},{-,},{,},{,-}};

 void dfs(int x,int y,int dir,int cnt){

     if(x<=||x>m||y<=||y>n||cnt>)

         return;

     if(vis[x][y][dir]<=cnt)//如果这个位置这个方向已经走过，且用了更小的转弯数，那就不用再走这个点了

         return;

     if(map[x][y]=='T'){

         flag=true;

         return;

     }

     if(map[x][y]!='.'&&map[x][y]!='S')

         return;

     vis[x][y][dir]=cnt;

     for(int i=;i<;i++) {

         int x1=x+d[i][];

         int y1=y+d[i][];

         if(dir==-)

             dfs(x1,y1,i,cnt);

         else if(dir!=i)

             dfs(x1,y1,i,cnt+);

         else

             dfs(x1,y1,i,cnt);

     }

 }

 int main(){

     int index,indey;

     scanf("%d %d",&m,&n);

     getchar();

     for(int i=;i<=m;i++){

         for(int j=;j<=n;j++){

             scanf("%c",&map[i][j]);

             if(map[i][j]=='S'){

                 index=i;

                 indey=j;

             }

         }

         getchar();

     }

     memset(vis,0x3f,sizeof(vis));//转弯数初始化为无限大

     dfs(index,indey,-,);//-1表示开始位置没有方向

     if(flag)

         printf("YES\n");

     else

         printf("NO\n");

 }

bfs，跟上面差不多的：

 #include<iostream>

 #include<cstring>

 #include<queue>

 using namespace std;

 const int N=1e3+;

 int vis[N][N][];

 int d[][]={{,},{-,},{,},{,-}};

 char map[N][N];

 int m,n;

 bool flag=false;

 struct node{

     int x,y,dir,cnt;

 }now,t,pre;

 //int num=0;

 void bfs(int stax,int stay){

     queue<node>q;

     t.x=stax;

     t.y=stay;

     t.dir=-;

     t.cnt=;

     q.push(t);

     while(!q.empty()){

         pre=q.front();

         q.pop();

         for(int i=;i<;i++){

             int x=pre.x+d[i][];

             int y=pre.y+d[i][];

             int cnt;

             if(pre.dir==-)//判断一下上次方向和当前要走的方向的关系

                 cnt=;

             else if(pre.dir==i)

                 cnt=pre.cnt;

             else if(pre.dir!=i)

                 cnt=pre.cnt+;

             if(x<=||x>m||y<=||y>n||cnt>)

                 continue;

             if(map[x][y]=='T'){//到达终点

                 flag=true;

                 return;

             }

             if(map[x][y]!='S'&&map[x][y]!='.')

                 continue;

             if(vis[x][y][i]<=cnt)//这个点这个方向已经有更优方案了

                 continue;

             vis[x][y][i]=cnt;

             now.x=x;

             now.y=y;

             now.dir=i;

             now.cnt=cnt;

 //            num++;

 //            printf("%d\n",num);

             q.push(now);

         }

     }

 }

 int main(){

     int index,indey;

     scanf("%d %d",&m,&n);

     getchar();

     for(int i=;i<=m;i++){

         for(int j=;j<=n;j++){

             scanf("%c",&map[i][j]);

             if(map[i][j]=='S'){

                 index=i;

                 indey=j;

             }

         }

         getchar();

     }

     memset(vis,0x3f,sizeof(vis));

     bfs(index,indey);

     if(flag)

         printf("YES\n");

     else

         printf("NO\n");

 }