# APCS 2022/10 題解
## ==巴士站牌==
### <font color="0E81A6">敘述</font>
[巴士站牌](https://zerojudge.tw/ShowProblem?problemid=i428)
### <font color="0E81A6">核心</font>
條件判斷
### <font color="0E81A6">思路</font>
不用陣列。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    int x1,x2,y1,y2;
    int Max=-1,Min=1000;
    int distance;
    scanf("%d%d%d",&n,&x1,&y1);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x2,&y2);
        distance=abs(x2-x1)+abs(y2-y1);
        Max=max(Max,distance);
        Min=min(Min,distance);
        x1=x2,y1=y2;
    }
    printf("%d %d",Max,Min);
}

## ==運貨站==
### <font color="0E81A6">敘述</font>
[運貨站](https://zerojudge.tw/ShowProblem?problemid=j123)
### <font color="0E81A6">核心</font>
模擬、二維陣列
### <font color="0E81A6">思路</font>
直接模擬就好。

#include <bits/stdc++.h>
using namespace std;
int r, c;
bool taken[40][60];
int used;
int no;
void A(int j)
{
	int i = c;
	for(;i >= 0;i--)
    {
		if(i == 0 || taken[j][i-1] || taken[j+1][i-1] || taken[j+2][i-1] || taken[j+3][i-1]) break;
	}
	if(i >= c) no++;
	else
	{
		taken[j][i] = true;
		taken[j+1][i] = true;
		taken[j+2][i] = true;
		taken[j+3][i] = true;
		used += 4;
	}
}
void B(int j)
{
	int i = c+2;
	for(;i >= 2;i--)
    {
		if(i == 2 || taken[j][i-3]) break;
	}
	if(i >= c) no++;
	else
	{
		taken[j][i] = true;
		taken[j][i-1] = true;
		taken[j][i-2] = true;
		used += 3;
	}
}
void C(int j)
{
	int i = c+1;
	for(;i >= 1;i--)
    {
		if(i == 1 || taken[j][i-2] || taken[j+1][i-2]) break;
	}
	if(i >= c) no++;
	else
    {
		taken[j][i] = true;
		taken[j+1][i] = true;
		taken[j][i-1] = true;
		taken[j+1][i-1] = true;
		used += 4;
	}
}
void D(int j)
{
	int i = c+2;
	for(;i >= 2;i--)
    {
		if(i == 2 || taken[j+1][i-3] || taken[j][i-1]) break;
	}
	if(i >= c) no++;
	else
	{
		taken[j+1][i] = true;
		taken[j+1][i-1] = true;
		taken[j+1][i-2] = true;
		taken[j][i] = true;
		used += 4;
	}
}
void E(int j)
{
	int i = c+1;
	for(;i >= 1;i--)
    {
		if(i == 1 || taken[j][i-1] ||taken[j+1][i-2] || taken[j+2][i-2]) break;
	}
	if(i >= c) no++;
	else
	{
		taken[j][i] = true;
		taken[j+1][i] = true;
		taken[j+2][i] = true;
		taken[j+1][i-1] = true;
		taken[j+2][i-1] = true;
		used += 5;
	}
}
int main(){
	int q;
	cin >> r >> c >> q;
	while(q--){
		char ch;
		int j;
		cin >> ch >> j;
		if(ch == 'A') A(j);
		if(ch == 'B') B(j);
		if(ch == 'C') C(j);
		if(ch == 'D') D(j);
		if(ch == 'E') E(j);
	}
	cout << r * c - used << ' ' << no << '\n';
}

## ==石窟探險==
### <font color="0E81A6">敘述</font>
[石窟探險](https://zerojudge.tw/ShowProblem?problemid=j124)
### <font color="0E81A6">核心</font>
DFS、Tree
### <font color="0E81A6">思路</font>
DFS就完事。

#include <bits/stdc++.h>
using namespace std;
long long sum = 0;
void dfs(int last)
{
    int n;
    cin >> n;
    if (!n) return;

    if (last) sum += abs(n-last);

    if (n & 1)
    {
        dfs(n);
        dfs(n);
        dfs(n);
    }
    else
    {
        dfs(n);
        dfs(n);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    dfs(0);
    cout << sum;
}

## ==蓋步道==
### <font color="0E81A6">敘述</font>
[蓋步道](https://zerojudge.tw/ShowProblem?problemid=j125)
### <font color="0E81A6">核心</font>
DFS、BFS、二分搜
### <font color="0E81A6">思路</font>
先二分搜最大高度差的最小值(可到達右下)，用DFS去做。
接著以此高度BFS就是答案。

#include<bits/stdc++.h>
using namespace std;
#define piii pair<pair<int,int>,int>
#define ff first.first
#define fs first.second
#define pii pair<int,int>
int n;
int height[300][300];
bool visit[300][300];
int di[4]={1,0,-1,0},dj[4]={0,1,0,-1};
int bfs(int hDiff)
{
    memset(visit,false,sizeof(visit));
    queue<piii> Q;
    Q.push({{0,0},0});
    pii target={n-1,n-1};
    while(!Q.empty())
    {
        int x=Q.front().ff,y=Q.front().fs;
        int route=Q.front().second;
        if(make_pair(x,y)==target) return route;
        Q.pop();
        for(int dir=0;dir<4;dir++)
        {
            int i=x+di[dir],j=y+dj[dir];
            if(i>=0&&i<n&&j>=0&&j<n&&!visit[i][j]&&abs(height[i][j]-height[x][y])<=hDiff)
            {
                Q.push({{i,j},route+1});
                visit[i][j]=true;
            }
        }
    }
}
bool dfs(int hDiff)
{
    memset(visit,false,sizeof(visit));
    vector<pii> stk;
    stk.push_back({0,0});
    while(!stk.empty())
    {
        int x=stk.back().first,y=stk.back().second;
        stk.pop_back();
        if(x==n-1&&y==n-1) return true;
        for(int dir=0;dir<4;dir++)
        {
            int i=x+di[dir],j=y+dj[dir];
            if(i>=0&&i<n&&j>=0&&j<n&&!visit[i][j])
            {
                int h=abs(height[i][j]-height[x][y]);
                if(h<=hDiff)
                {
                    stk.push_back({i,j});
                    visit[i][j]=true;
                }
            }
        }
    }
    return false;
}
int findh()
{
    int l=0,r=1e6,mid;
    while(l<r)
    {
        mid=(l+r)/2;
        bool can=dfs(mid);
        if(can) r=mid;
        else l=mid+1;
    }
    return l;
}
int main()
{
   scanf("%d",&n);
   for(int i=0;i<n;i++)
   {
       for(int j=0;j<n;j++) scanf("%d",&height[i][j]);
   }
   int maxhDiff=findh();
   printf("%d\n%d\n",maxhDiff,bfs(maxhDiff));
}