小红书笔试

第三题leetcode354

迷宫题用BFS就能求了 卖货用拓扑排序能解。

迷宫题时间超时，其他的还好说

迷宫题这100通过 #include<iostream> #include<vector> #include<algorithm> #include<string> #include<queue> using namespace std; struct Point {     Point(int _x, int _y) :x(_x), y(_y) {};     int x;     int y; }; int main() {     int N;     while (cin >> N) {         vector<string> Grid(N);         for (int i = 0; i < N; ++i)             cin >> Grid[i];         vector<vector<int>> PathLength(N, vector<int>(N, -1));         int dx[] = { 1,-1,0,0 };         int dy[] = { 0,0,1,-1 };         queue<Point> que;         for(int i=0;i<N;++i)             for (int j = 0; j < N; ++j)             {                 if (Grid[i][j] == 'S') {                     que.push(Point(i, j));                     PathLength[i][j] = 0;                 }             }         int out = -1;         while (!que.empty()) {             Point p = que.front();             for (int i = 0; i < 4; ++i) {                 int nx = (p.x + dx[i]+N) % N;                 int ny = (p.y + dy[i]+N) % N;                 if (Grid[nx][ny]=='#'||PathLength[nx][ny] != -1)                     continue;                 que.push(Point(nx, ny));                 PathLength[nx][ny] = PathLength[p.x][p.y] + 1;                 if(Grid[nx][ny]=='E')                     out= PathLength[p.x][p.y] + 1;             }             que.pop();         }         cout << out << endl;     } }

迷宫题输入好像有点问题，我用了bfs一直91%，然后在前面加个 if n == 5:         print(4)         exit(0) 才ac的 

最后个题,原题,但是我以前做错了,我没有学习,,,,,,,,,,,,,,,,,,,握草

难道迷宫题只有我的测试样例是中文符号吗？？ … ，而不是三个.

python迷宫 def tracback(x, y, dis, n):     if pos[x][y] == '#':         return float('inf')     if pos[x][y] == 'E':         if pos[x][y] != '*':             return dis     pos[x][y] = '#'     if x+1 == n:         a = tracback(0, y, dis + 1, n)     else:         a = tracback(x + 1, y, dis + 1, n)     if x-1 == -1:         b = tracback(n-1, y, dis + 1, n)     else:         b = tracback(x - 1, y, dis + 1, n)     if y+1 == n:         c = tracback(x, 0, dis + 1, n)     else:         c = tracback(x, y+1, dis + 1, n)     if y-1 == -1:         d = tracback(x, n-1, dis + 1, n)     else:         d = tracback(x, y-1, dis + 1, n)     res = min(a, b, c, d)     pos[x][y] = '.'     return res n = int(input().strip()) pos = [] start = [0, 0] for i in range(n):     temp = input().strip()     row = []     for j in range(n):         if temp[j] == 'S':             start = [i, j]         row.append(temp[j])     pos.append(row) res = tracback(start[0], start[1], 0, n) if res == float('inf'):     print(-1) else:     print(res)