---
tags: 解題報告
---

# j125. 4. 蓋步道
題目連結: [Zerojudge](https://zerojudge.tw/ShowProblem?problemid=j125)

## 題目說明
給一數字 $n$ 與 $n*n$ 的陣列, 求出能由左上走到右下所需的最小數字差及所需步數

## 想法

1. 輸入
2. 二分搜
3. BFS

## 參考答案
:::spoiler 點我展開
Runtime: 0.1s
Memory: 1008KB
時間複雜度: $O(log(n^2))$
空間複雜度: $O(2n^2)$

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

int area[301][301];
int move_x[4]={1, -1, 0, 0},
	move_y[4]={0, 0, 1, -1};
int visted[301][301];
int n;

void init(){
	for (int i=1; i<=n; i++){
		for (int j=1; j<=n; j++) visted[i][j]=-1;
	}
}

void bfs(int high){
	init();
	queue<pair<int, int> > q;
	q.push(make_pair(1, 1));
	visted[1][1] = 0;
	while (q.size() > 0){
		pair<int, int> p = q.front();
		q.pop();
		int x = p.first,
			y = p.second;
		for (int m=0; m<4; m++){
			int tx = x + move_x[m],
				ty = y + move_y[m];
			if (tx <= 0 or ty <= 0 or tx > n or ty > n) continue;
			if (abs(area[tx][ty] - area[x][y]) <= high and (visted[tx][ty] == -1)){
				q.push(make_pair(tx, ty));
				visted[tx][ty] = visted[x][y]+1;
			}
		}
	}
}

signed main(){
	cin>>n;
	for (int i=1; i<=n; i++){
		for (int j=1; j<=n; j++) cin>>area[i][j];
	}
	int l=0, r=1e6;
	while (l <= r){
		int m = (l+r)/2;
		bfs(m);
		if (visted[n][n] !=  -1) r = m-1;
		else l = m+1;
	}
	bfs(l);
	cout<<l<<"\n"<<visted[n][n];
}

[Github](https://github.com/henryleecode23/solve_record/tree/main/zerojudge/j125)
:::

## 解釋
### 輸入
建立 $300*300$ 的陣列做儲存
這裡開$301*301$之後計算比較直覺

int area[301][301];

搭配巢狀迴圈接收輸入

cin>>n;
for (int i=1; i<=n; i++){
    for (int j=1; j<=n; j++) cin>>area[i][j];
}

### [二分搜](/R_LXj5WkRwWJAVHfG3vEiA)
因為高度範圍最大能到$10^6$, 如果從1開始一個一個數字下去跑很可能會TLE
因此使用二分搜加快速度, 來找出能走到終點的最大高度差
如果能走到終點就把高度往下, 走不到就往上找

while (l <= r){
    int m = (l+r)/2;
    bfs(m);
    if (visted[n][n] !=  -1) r = m-1;
    else l = m+1;
}

### [BFS](/M-EVnoAlR9KD2Cn21wz5NA)
找最短路徑長度用BFS是基礎

void bfs(int high){
    init();
    queue<pair<int, int> > q;
    q.push(make_pair(1, 1));
    visted[1][1] = 0;
    while (q.size() > 0){
    	pair<int, int> p = q.front();
    	q.pop();
    	int x = p.first,
    	    y = p.second;
    	for (int m=0; m<4; m++){
    	    int tx = x + move_x[m],
    	    	ty = y + move_y[m];
    	    if (tx <= 0 or ty <= 0 or tx > n or ty > n) continue;
    	    if (abs(area[tx][ty] - area[x][y]) <= high and (visted[tx][ty] == -1)){
                q.push(make_pair(tx, ty));
                visted[tx][ty] = visted[x][y]+1;
    	    }
    	}
    }
}

## 心得
這題是2022 10月的APCS 第四題, 當初考的時候還不知道二分搜這東西結果只撈到部份分
現在覺得二分搜超神

---
{%hackmd @henry-lee-code23/dark-theme %}