当前位置：首页 > news >正文

东莞大岭山森林公园/seo管理工具

news 2025/7/2 3:53:25

东莞大岭山森林公园,seo管理工具,深圳外贸建站网络推广哪家好,交易所源码说一下我在时间复杂度上的优化，总共2点不使用类，使用int代表x,y,正副三种状态从终点走到起点，而不是从起点走到终点解释一下为什么不用类，因为不想用，所以不用。一个int型的数的数值长度占了31位，我通…

在这里插入图片描述

说一下我在时间复杂度上的优化，总共2点

不使用类，使用int代表x,y,正副三种状态
从终点走到起点，而不是从起点走到终点

解释一下为什么不用类，因为不想用，所以不用。
一个int型的数的数值长度占了31位，我通过二进制取数值的第30位判断当前节点是+还是-。如果第30位是1，那么就是+，否则就是-
坐标通过一个公式转换 y * n + x 这个公式可以将二维的数组转为一维的数组，我们每次访问二维数组，都需要先访问Array[] 然后在Array[]里找到[] ,通过下标找到对应元素，这样子等于访问了两次对象。而使用公式转换后的下标，可以省去一次访问元素的代价。
因为是最短路径，bfs每次寻找周围一圈，如果最先能得到的路径肯定是最优路径，所以选择bfs，本题使用dfs可能会比bfs慢点，因为bfs需要把每条路径的长度最后进行一个比较，输出最短的那一条，慢就慢在这里。

public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();char[][] grid = new char[n][n];scanner.nextLine(); // 吸收掉回车int startHash = 0;int endHash = 0;for (int i = 0; i < n; i++) {String[] s = scanner.nextLine().split(" ", n);for (int j = 0; j < n; j++) {char c = grid[i][j] = s[j].charAt(0);if (c == 'A') {startHash = i * n + j;} else if (c == 'B') {endHash = i * n + j;}}}/*for (char[] c : grid) {System.out.println(Arrays.toString(c));}*/boolean[] viewed = new boolean[n * n]; // bfs必备表示是否访问过的数组Queue<Integer> queue = new LinkedList<>();// 手动加入终点一圈的节点 并且viewed// 是否为正负 -> 根据 1 << 30 是否等于1决定int bx = endHash % n;int by = endHash / n;viewed[endHash] = true;if (bx + 1 < n) {int hashx1 = endHash + 1;viewed[hashx1] = true;if (checkPosNeg(bx+1,by,grid)) {hashx1 |= 1 << 30;}queue.offer(hashx1);}if (bx - 1 > -1) {int hash1x = endHash - 1;viewed[hash1x] = true;if (checkPosNeg(bx-1,by,grid)) {hash1x |= 1 << 30;}queue.offer(hash1x);}if (by + 1 < n) {int hashy1 = endHash + n;viewed[hashy1] = true;if (checkPosNeg(bx,by+1,grid)) {hashy1 |= 1 << 30;}queue.offer(hashy1);}if (by - 1 > -1) {int hash1y = endHash - n;viewed[hash1y] = true;if (checkPosNeg(bx,by-1,grid)) {hash1y |= 1 << 30;}queue.offer(hash1y);}int pathLength = 0;while (!queue.isEmpty()) {pathLength ++;int len = queue.size();for (int i = 0; i < len; i++) {int hash = queue.poll();boolean pos = (hash & (1 << 30)) > 0;if (pos) {hash &= (1 << 30) - 1;}if (hash == startHash) {System.out.println(pathLength);System.exit(0);}int x = hash % n;int y = hash / n;if (x + 1 < n && !viewed[hash+1] && (pos != (grid[y][x+1] == '+') || grid[y][x+1] == 'A')) {int hashx1 = hash + 1;viewed[hashx1] = true;if (checkPosNeg(x+1,y,grid)) {hashx1 |= 1 << 30;}queue.offer(hashx1);}if (x - 1 > -1 && !viewed[hash-1] && (pos != (grid[y][x-1] == '+') || grid[y][x-1] == 'A')) {int hash1x = hash - 1;viewed[hash1x] = true;if (checkPosNeg(x-1,y,grid)) {hash1x |= 1 << 30;}queue.offer(hash1x);}if (y + 1 < n && !viewed[hash+n] && (pos != (grid[y+1][x] == '+') || grid[y+1][x] == 'A')) {int hashy1 = hash + n;viewed[hashy1] = true;if (checkPosNeg(x,y+1,grid)) {hashy1 |= 1 << 30;}queue.offer(hashy1);}if (y - 1 > -1 && !viewed[hash-n] && (pos != (grid[y-1][x] == '+') || grid[y-1][x] == 'A')) {int hash1y = hash - n;viewed[hash1y] = true;if (checkPosNeg(x,y-1,grid)) {hash1y |= 1 << 30;}queue.offer(hash1y);}}}System.out.println(-1);}public static boolean checkPosNeg(int x, int y, char[][] grid) {return grid[y][x] == '+';}
}