CodeForces - 586D Phillip and Trains

这道题是一道搜索题

但是如果没有读懂或者或者拐过弯就很麻烦

最多26个火车那么每一个周期（人走一次车走一次）就要更改地图的状态而且操作复杂容易超时出错

利用相对运动

计周期为人向上或向下或不动一步 + 向右三步

这样就变为走迷宫问题了

同样要注意

1、去重数组或者将以前访问过的点置为其他符号避免重复访问

2、还有因为每次是三步三步的往右走所以最后的边界可能不够可以再扩充三列

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <queue>

 using namespace std;

 typedef pair<int, int> P;

 int T,t;

 //bool vis[3][104];

 char maze[][];

 P start;

 bool check(int x ,int y)

 {

     if (x >  || x < ) return false;

     if (maze[x][y] != '.') return false;

     return true;

 }

 bool bfs()

 {

     queue<P> que;

     P crt = start;

     crt.second++;

     if (crt.second >= t) return true;

     if (maze[crt.first][crt.second] == '.') que.push(crt);

     while (!que.empty())

     {

         P crt = que.front();

         que.pop();

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

         {

             int tx = crt.first + i, ty = crt.second;

             if ( !check(tx, ty) ) continue;

             bool isSafe = true;

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

             {

                 if (!check(tx, ty+j))

                 {

                     isSafe = false;

                     break;

                 }

             }

             if (isSafe)

             {

                 if (ty+ >= t) return true;

                 else

                 que.push(P(tx, ty+));

             }

         }

         maze[crt.first][crt.second] = 'A';//使用去重数组的话 内存超了 当访问完这个点以后 做标记 以后不再访问

     }

     return false;

 }

 int main()

 {

     freopen("in.txt", "r", stdin);

     scanf("%d", &T);

     int k;

     while (T--)

     {

         scanf("%d%d", &t, &k);

         //memset(vis, false, sizeof(vis));

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

         {

             getchar();

             for (int j = ; j < t; j++)

             {

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

                 if (maze[i][j] == 's')

                 {

                     start.first = i;

                     start.second = j;

                 }

             }

             for (int j = t; j < t+; j++)

             {

                 maze[i][j] = '.';

             }

         }

         if(bfs()) printf("YES\n");

         else printf("NO\n");

     }

     return ;

 }

巴特西

CodeForces - 586D Phillip and Trains

最新文章

热门文章