RT，记得 at 我。

$Q1$

谁能帮我分析一下下面代码的时间复杂度 QwQ（不是我写的）。

#include <bits/stdc++.h>
using namespace std;
const int N=42;
bool flag[N][N];
long long n,m,a,b,ans;
void dfs(int x,int y,int z){
	if(z==a){ans++;return;}
	if(x>n){return;}
	y++;if(y>m) x++,y=1;
	dfs(x,y,z);
	y--;if(y<1) x--,y=m;
	if(flag[x][y]==0&&flag[x+1][y]==0&&flag[x+2][y]==0&&x+2<=n){
		flag[x][y]=flag[x+1][y]=flag[x+2][y]=1;
		y++;if(y>m) x++,y=1;
		dfs(x,y,z+1);
		y--;if(y<1) x--,y=m;
		flag[x][y]=flag[x+1][y]=flag[x+2][y]=0;
	}
	if(flag[x][y]==0&&flag[x][y+1]==0&&flag[x][y+2]==0&&y+2<=m){
		flag[x][y]=flag[x][y+1]=flag[x][y+2]=1;
		y++;if(y>m) x++,y=1;
		dfs(x,y,z+1);
		y--;if(y<1) x--,y=m;
		flag[x][y]=flag[x][y+1]=flag[x][y+2]=0;
	}
}
int main()
{
	scanf("%lld %lld %lld %lld",&n,&m,&a,&b);
	dfs(1,1,0);
	printf("%lld",ans);
	return 0;
}

$Q2$

给定一个 $n\times m$ 的地图和每个点的海拔，有的点是障碍不能走（#）。

相邻两点直接走过的费用是其海拔差的绝对值，求从 $(1 ,1)$ 走到 $(n ,m)$ 的最小费用。

$1\le \text{海拔值}\le 1000$，$1\le n\times m \le 2\times 10^5$。

请问下面的四份代码，在以下数据下，Code $1$，$2$ 输出 $6252$，Code $3$，$4$ 输出 $6774$，这是为什么？我看不出区别。

数据：

25 20
.....#..............
.....#..............
.....#.........#....
..........#..#......
.#..#...............
..................#.
#...#.......#.......
.#....#.............
....................
....................
....#..#............
....................
.............#.....#
....................
.....#..............
..............#.....
.#....#..#..........
....................
.................#..
....................
....................
....................
.............#......
....#...............
......#.............
272 646 862 325 226 843 680 331 404 235 120 278 503 675 509 471 283 309 641 239 
446 306 394 7 576 683 181 351 244 620 801 577 28 744 580 192 345 824 471 804 
280 516 501 408 416 719 663 469 815 487 70 831 101 607 697 229 961 60 563 875 
372 762 54 497 930 763 635 81 341 461 7 598 496 621 484 626 189 249 118 366 
322 661 820 324 375 645 772 142 624 290 517 603 416 688 451 947 123 817 217 65 
811 758 445 984 847 45 857 149 702 764 760 883 857 170 141 848 94 559 235 583 
250 752 35 763 965 997 455 8 762 5 575 78 845 403 246 405 916 749 811 254 
882 91 65 282 576 565 748 967 547 733 222 130 270 998 261 936 192 10 326 923 
493 265 364 704 421 219 151 854 392 342 925 938 709 423 591 323 322 442 517 196 
693 180 128 449 112 632 191 314 516 596 890 3 286 891 311 469 256 537 49 605 
625 617 737 804 986 674 160 728 361 582 746 64 730 178 356 630 195 418 622 149 
641 548 166 668 958 902 888 279 968 585 524 696 128 216 383 902 260 751 460 943 
565 936 257 98 395 789 971 12 832 854 932 646 18 189 648 474 894 161 971 695 
779 184 253 416 306 965 768 716 140 177 692 482 496 18 175 64 595 682 34 127 
736 134 84 876 899 17 411 796 290 198 648 621 150 258 721 707 553 544 797 846 
396 555 730 996 429 716 790 469 952 698 405 703 680 637 293 271 439 751 756 993 
236 289 780 296 57 202 782 494 840 867 172 644 309 878 731 734 865 237 223 692 
46 937 931 634 903 221 253 1000 915 840 945 761 845 383 539 255 668 440 629 852 
375 787 313 655 992 420 380 798 496 185 474 539 404 103 795 580 400 444 835 182 
951 94 179 506 774 632 647 493 435 851 706 116 262 299 425 743 820 260 473 997 
844 426 726 440 644 16 262 359 858 787 812 317 768 140 848 604 315 976 115 940 
1000 66 850 884 866 737 544 244 403 484 397 861 179 506 957 393 619 901 417 864 
140 896 57 880 888 181 514 758 250 319 917 968 510 282 580 83 4 768 705 766 
841 528 651 765 28 886 361 788 844 990 186 910 912 223 320 500 436 352 647 469 
308 946 893 537 821 148 917 206 459 164 597 403 279 69 737 937 717 861 126 854 

Code $1$：

# include <bits/stdc++.h>

# define int long long
# define up(i ,x ,y) for (int i = x ; i <= y ; i ++)
# define dn(i ,x, y) for (int i = x ; i >= y ; i --)

using namespace std;

inline int read (){int s = 0 ; bool w = 0 ; char c = getchar () ; while (!isdigit (c)) {w |= (c == '-') ,c = getchar () ;} while (isdigit (c)){s = (s << 1) + (s << 3) + (c ^ 48) ; c = getchar ();}return w ? -s : s;}
inline void write (int x){if (x < 0) putchar ('-') ,x = -x; if (x > 9) write (x / 10) ; putchar (x % 10 | 48);}
inline void writesp (int x){write (x) ,putchar (' ');}
inline void writeln (int x){write (x) ,putchar ('\n');}

# define inf 1e16
const int N = 2e5 + 10 ,M = 1e6 + 10;
int n ,m ,dis[N];
bool vis[N];
vector <int> a[N] ,high[N];
struct EDGE {int to ,w ,nxt;}edge[M]; int cnt ,head[N];
const int fx[] = {0 ,-1 ,0 ,1} ,fy[] = {-1 ,0 ,1 ,0};

inline int get (int i ,int j) {
	return (i - 1) * m + j;
} inline void add (int u ,int v ,int w) {
	edge[++ cnt] = {v ,w ,head[u]} ,head[u] = cnt;
}
inline int dij () {
  # define PII pair <int ,int>
  priority_queue < PII ,vector < PII > ,greater < PII > > q;
  q.push ({0 ,1});
  up (i ,0 ,get(n ,m)) dis[i] = inf ,vis[i] = 0;
  dis[1] = 0;
  while (!q.empty()) {
  	int u = q.top().second;
  	q.pop ();
  	if (vis[u]) continue;
  	vis[u] = 1;
  	for (int i = head[u] ; i ; i = edge[i].nxt){
  		int v = edge[i].to ,w = edge[i].w;
//  		cout << v<< endl;
		if (dis[v] > dis[u] + w) {
			dis[v] = dis[u] + w;
			q.push ({dis[v] ,v});
		}
	}
  }
  return dis[get(n ,m)] == dis[0] ? -1 : dis[get(n ,m)];
}
signed main(){
  // up (test ,1 ,36){
    // fun (test);
  n = read () ,m = read ();
 writeln (get(n ,m));
  up (i ,1 ,get(n ,m)) head[i] = 0 ,a[i].clear() ,high[i].clear();
  cnt = 0;
  up (i ,1 ,n) {
  	a[i].push_back(0);
  	up (j ,1 ,m) {
  	  char x ; cin >> x;
	  a[i].push_back (x == '*' ? 0 : 1);	
	}
  }
  up (i ,1 ,n) {
  	high[i].push_back (0);
  	up (j ,1 ,m) high[i].push_back (read ());
  }
  up (i ,1 ,n) up (j ,1 ,m) {
  	if (a[i][j] == '*') continue;
  	up (dir ,0 ,3) {
  	  int ax = fx[dir] + i ,ay = fy[dir] + j;
	  if (ax >= 1 && ay >= 1 && ax <= n && ay <= m && a[ax][ay] != 0) add(get(i ,j) ,get(ax ,ay) ,abs(high[ax][ay] - high[i][j])); 	
	}
  } writeln(dij ());
  // }  

  return 0;
}

Code $2$：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};

struct Cell {
    int x, y;
    int cost;
    bool operator>(const Cell& other) const {
        return cost > other.cost;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<char>> grid(n, vector<char>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }
    
    vector<vector<int>> high(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> high[i][j];
        }
    }
    
    vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
    dist[0][0] = 0;
    
    priority_queue<Cell, vector<Cell>, greater<Cell>> pq;
    pq.push({0, 0, 0});
    
    while (!pq.empty()) {
        Cell current = pq.top();
        pq.pop();
        
        if (current.x == n - 1 && current.y == m - 1) {
            cout << current.cost << endl;
            return 0;
        }
        
        if (current.cost > dist[current.x][current.y]) {
            continue;
        }
        
        for (int i = 0; i < 4; ++i) {
            int nx = current.x + dx[i];
            int ny = current.y + dy[i];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] != '*') {
                int new_cost = current.cost + abs(high[nx][ny] - high[current.x][current.y]);
                if (new_cost < dist[nx][ny]) {
                    dist[nx][ny] = new_cost;
                    pq.push({nx, ny, new_cost});
                }
            }
        }
    }
    
    cout << -1 << endl;
    return 0;
}

Code $3$：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int INF = 1e18;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

inline int read() {
    int X = 0;
    bool flag = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') flag = 0;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        X = (X << 1) + (X << 3) + ch - '0';
        ch = getchar();
    }
    if (flag) return X;
    return ~(X - 1);
}

inline void write(int X) {
    if (X < 0) {
        X = ~(X - 1);
        putchar('-');
    }
    if (X > 9) write(X / 10);
    putchar(X % 10 + '0');
}

inline void writeln(int X) {
    write(X);
    putchar('\n');
}

int n, m;
vector<string> grid;
vector<vector<int>> high;
vector<vector<int>> dist;

signed main() {
    n = read();
    m = read();
    
    grid.resize(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    
    // 检查终点是否为陷阱
    if (grid[n-1][m-1] == '*') {
        writeln(-1);
        return 0;
    }
    
    high.resize(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            high[i][j] = read();
        }
    }
    
    // 初始化距离数组
    dist.assign(n, vector<int>(m, INF));
    dist[0][0] = 0;
    
    // 优先队列 (距离, x, y)
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    pq.emplace(0, 0, 0);
    
    while (!pq.empty()) {
        auto [d, x, y] = pq.top();
        pq.pop();
        
        // 到达终点
        if (x == n-1 && y == m-1) {
            writeln(d);
            return 0;
        }
        
        // 已找到更短路径
        if (d > dist[x][y]) continue;
        
        // 探索四个方向
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == '.') {
                int new_dist = d + abs(high[nx][ny] - high[x][y]);
                if (new_dist < dist[nx][ny]) {
                    dist[nx][ny] = new_dist;
                    pq.emplace(new_dist, nx, ny);
                }
            }
        }
    }
    
    // 无法到达终点
    writeln(-1);
    return 0;
}

Code $4$：

# include <bits/stdc++.h>

# define rint register int
//# define int long long

int read() {int s = 0 , w = 0; char c = getchar(); while (!isdigit(c)) w |= (c == '-') , c = getchar(); while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48) , c = getchar(); return w ? -s : s;}
void write(int x) {if (x < 0) putchar('-') , x = ~ (x - 1); if (x > 9) write(x / 10); putchar(x % 10 | 48);}
void writesp(int x) {write(x) , putchar(' '); }
void writeln(int x) {write(x) , putchar('\n');}

using namespace std;

const int N = 3010;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
const int inf = 1e9;

struct node {
    int x;
    int y;
    int val;
    bool operator > (const node& x) const {return val > x.val;}
};

int n, m;
vector <vector <int> > high;
vector <vector <int> > dist;
vector <vector <bool> > f;

priority_queue <node, vector<node>, greater<node> > pq;

int dij (vector <vector <int> > high, vector <vector <int> > dist, vector <vector <bool> > f) {
	if (f[n][m] == 1) return -1;
  for (int i = 1; i <= n; i ++)
    for (rint j = 1; j <= m; j ++)
      dist[i][j] = inf;
  dist[1][1] = 0;
  pq.push({1, 1, 0});
  while (!pq.empty()) {
    node now = pq.top();
    pq.pop();
    int nowx = now.x, nowy = now.y;
    if (nowx == n && nowy == m) return now.val;
    if (now.val > dist[nowx][nowy]) continue;
    for (rint i = 0; i < 4; i ++) {
      int nx = now.x + dx[i], ny = now.y + dy[i];
      if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && f[nx][ny] == 0) {
        int nv = now.val + abs(high[nx][ny] - high[nowx][nowy]);
        if (nv < dist[nx][ny]) dist[nx][ny] = nv, pq.push({nx, ny, nv});
      }
    }
  }
  return -1;
}

signed main() {
	n = read (),
	m = read ();
  high.resize (n + 1, vector <int> (m + 1)),
  dist.resize (n + 1, vector <int> (m + 1)),
  f.resize (n +1 , vector <bool> (m + 1));
  for (rint i = 1; i <= n; i ++)
    for (rint j = 1; j <= m; j ++) {
      char x;
      cin >> x;
      if (x == '.') f[i][j] = 0;
      else f[i][j] = 1;
		}
  for (rint i = 1; i <= n; i ++)
    for (rint j = 1; j <= m; j ++)
      high[i][j] = read ();
	write (dij (high, dist, f));
  return 0;
} // not by Dream_Stars qwq