【HDOJ】2102 A计划

BFS，不过有很多地方需要注意，比如传送机传送到另一个传送机。还有要注意格式。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <queue>

 using namespace std;

 typedef struct node_st{

     int x, y, s, t;

     node_st() {}

     node_st(int ss, int xx, int yy, int tt) {s=ss;x=xx;y=yy;t=tt;}

 } node_st;

 char map[][][];

 char visit[][][];

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

 int n, m, time;

 bool bfs(int sx, int sy, int ss) {

     queue<node_st> nodes;

     int x, y, t, s;

     bool success = false;

     memset(visit, , sizeof(visit));

     visit[ss][sx][sy] = ;

     nodes.push(node_st(ss,sx,sy,));

     while ( !nodes.empty() ) {

         node_st node = nodes.front();

         if (node.t > time)

             break;

         if (map[node.s][node.x][node.y] == 'P') {

             success = true;

             break;

         }

         nodes.pop();

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

             x = node.x + direct[i][];

             y = node.y + direct[i][];

             s = node.s;

             t = node.t + ;

             if (visit[s][x][y] || x< || x>=n || y< || y>=m)

                 continue;

             if (map[s][x][y]=='#') {

                 visit[s][x][y] = ;

                 s = !s;

                 if (visit[s][x][y])

                     continue;

             }

             if (map[s][x][y]=='#' || map[s][x][y]=='*') {

                 visit[s][x][y] = ;

             } else if (map[s][x][y]=='P' || map[s][x][y]=='.') {

                 visit[s][x][y] = ;

                 nodes.push(node_st(s,x,y,t));

             }

         }

     }

     return success;

 }

 int main() {

     int case_n;

     int i;

     scanf("%d", &case_n);

     while (case_n--) {

         scanf("%d %d %d%*c", &n, &m, &time);

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

             scanf("%s%*c", map[][i]);

         getchar();

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

             scanf("%s%*c", map[][i]);

         if (bfs(, , ))

             printf("YES\n");

         else

             printf("NO\n");

     }

     return ;

 }