商务合作:179001057@qq.com

XiangTan Univ. invitational Contest 2010 I,ROBOT

技术2022-05-12  0


某平台价值19860元的编程课程资料免费领取【点我领取】


广搜,之前用四个方向不标记的广搜方法错了。。记得标记四个方向,这题很纠结。。。

# include<iostream>#include <queue>using namespace std;struct Node{       int x, y;       int dir;       int step;       int judge[4];       bool operator <(const Node t)const    {        return step > t.step;    }      }start;Node next, pre;const int Go[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int n, m, ex, ey;char map[110][110];bool visitedm[110][110][4];int ans;bool check(int x, int y){     return (x >= 0&& x < n && y >= 0 && y < m);     }void Bfs(){     priority_queue  <Node> Que;     memset(visitedm, false, sizeof(visitedm));     start.judge[0] = 1;     Que.push(start);     int kkk = 0;     while (!Que.empty()){           pre = Que.top();           Que.pop();           kkk ++;           if (map[pre.x][pre.y] == 'T'){                                 ans = pre.step;                 return ;                   }           for (int i = 0; i < 4; i ++){               if (i == pre.dir){                  int xx = pre.x + Go[i][0];                  int yy = pre.y + Go[i][1];                  if (check(xx, yy) && !visitedm[xx][yy][i] && map[xx][yy] != '#'){                     visitedm[xx][yy][i] = true;                     next.step = pre.step+1;                     if (map[xx][yy] == 'T'){                                        ans = next.step;                        return ;                             }                     next.x = xx, next.y = yy;                             next.dir = i;                     Que.push(next);                     }                    }               else {                    if (pre.dir == 0 && i == 1)continue;                    if (pre.dir == 1 && i == 0)continue;                    if (pre.dir == 2 && i == 3)continue;                    if (pre.dir == 3 && i == 2)continue;                    next.x = pre.x, next.y = pre.y;                    next.dir = i;                    next.step = pre.step + 1;                    if (!visitedm[pre.x][pre.y][i]){                       visitedm[pre.x][pre.y][i] = true;                       Que.push(next);                        }               }           }          }       }int main(){    int t;    scanf("%d", &t);    while (t --){          scanf("%d %d", &n, &m);          for (int i = 0; i <n; i ++){              scanf("%s", map[i]);                 for (int j = 0; j < m; j ++){                  if (map[i][j] == 'S'){                     start.x = i;                     start.y = j;                     start.step = 0;                     start.dir = 0;                     memset(start.judge, 0, sizeof(start.judge));                         }              }              }          ans = -1;          Bfs();          printf("%d/n", ans);                 }    return 0;    }

 


最新回复(0)