# Else OJ

## 網站
- [LIOJ](https://oj.lidemy.com/problem)
> 難度：⭐

## LIOJ

### #1014
- [不九人世](https://oj.lidemy.com/problem/1014)

/*
解題思路：
計算1 ~ n有多少9，再用n減掉

特性為
10有1個、20有2個；
100有19個、200有38個；
...

例如13452，將10000提出計算，累積到counter
接著以3452，將1000提出計算*3，累積到counter
...
最後以n - counter
*/
#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int count_nines(int n) {
    int count = 0;
    for (int i = 1; i <= n; ++i) {
        int num = i;
        while (num != 0) {
            int digit = num % 10;
            if (digit == 9) {
                ++count;
                break;
            }
            num /= 10;
        }
    }
    return count;
}

int main() {
    int N, n, counter = 0;
    string str;
    cin >> N;
    n = N;
    //N為原始輸入，n為原始值隨計算減少直到 = 0
    while (n > 0) {
        str = to_string(n);
        //抓開頭計算
        counter += int(str.front() - '0') * count_nines(pow(10, str.size() - 1));
        //去掉第一位數
        n -= int(str.front() - '0') * pow(10, str.size() - 1);
    }
    cout << N - counter << endl;

    return 0;
}

### #1019
- [1019_一條路走到黑](https://oj.lidemy.com/problem/1019)

//DFS 二維vector解題
//此題由於不會有岔路跟死路需返回的情況，只有一條路可以走，故可用此解法
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int w, h;
    cin >> w >> h;

    // 宣告一個二維 vector，初始值為 '.'
    vector<vector<char>> maze(h, vector<char>(w, '.'));

    // 讀入迷宮地圖
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> maze[i][j];
        }
    }

    int x = 0, y = 0, steps = 0;
    
    // 從 (0,0) 走到 (w-1,h-1)
    while (x != w - 1 || y != h - 1) {  //當還沒走到右下角前就繼續
        maze[y][x] = '#';  // 走過的路標記為牆壁，避免重複走

        // 優先往右或下走，如果右或下是路就走，否則往左或上走
        if (x < w - 1 && maze[y][x + 1] == '.') {
            x++;
        }
        else if (y < h - 1 && maze[y + 1][x] == '.') {
            y++;
        }
        else if (x > 0 && maze[y][x - 1] == '.') {
            x--;
        }
        else if (y > 0 && maze[y - 1][x] == '.') {
            y--;
        }

        steps++;
    }

    cout << steps << endl;
    return 0;
}

### #1033
- [1033_最近點對](https://oj.lidemy.com/problem/1033)

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>

using namespace std;

struct Point {
    int x;
    int y;
};

int main() {
    int N, mP1, mP2;
    double now_dist, min_dist = INT_MAX;
    
    cin >> N;
    
	vector<Point> points(N);
    
    for (int i = 0; i < N; i++) {
        cin >> points[i].x >> points[i].y;
    }

    //假設有5號，
    //i=0 vs j=1,2,3,4
    //i=1 vs j=2,3,4
	//i=2 vs j=3,4
	//i=3 vs j=4
    for (int i = 0; i < N - 1; i++) {
        for (int j = i + 1; j < N; j++) {
            now_dist = sqrt(pow(points[i].x - points[j].x, 2) + pow(points[i].y - points[j].y, 2));
            if (now_dist < min_dist) {
				min_dist = now_dist;
                mP1 = i;
                mP2 = j;
            }
        }
    }
    
    if (points[mP1].x < points[mP2].x) {
        cout << points[mP1].x << ' ' << points[mP1].y << endl;
        cout << points[mP2].x << ' ' << points[mP2].y;
    }
    else if (points[mP1].x > points[mP2].x) {
        cout << points[mP2].x << ' ' << points[mP2].y << endl;
        cout << points[mP1].x << ' ' << points[mP1].y;
    }
    else {
        if (points[mP1].y < points[mP2].y) {
            cout << points[mP1].x << ' ' << points[mP1].y << endl;
            cout << points[mP2].x << ' ' << points[mP2].y;
        }
        else {
            cout << points[mP2].x << ' ' << points[mP2].y << endl;
            cout << points[mP1].x << ' ' << points[mP1].y;
        }
    }

    return 0;
}

### #1034
- [1034_凱薩加密](https://oj.lidemy.com/problem/1034)

#include <iostream>
#include <string>

using namespace std;

int main() {
	int n, size, i_tmp;
	string S;
	
	cin >> n >> S;
	size = S.size();
	
	for (int i = 0; i < size; i++) {
		n %= 26;
		i_tmp = int(S[i]) + n;
		if (i_tmp > 122) {
			i_tmp = i_tmp - 122 + 97 - 1;
		}
		S[i] = char(i_tmp);
	}
	cout << S << endl;

	return 0;
}

### #1048
- [1048_最大連續和](https://oj.lidemy.com/problem/1048)

#include <iostream>
#include <climits>

using namespace std;

int main() {
    int n;
    cin >> n;

    int max_sum = INT_MIN; // 設定一個非常小的初值
    int sum = 0;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        sum += x;
        max_sum = max(max_sum, sum);
        sum = max(sum, 0);
    }

    cout << max_sum << endl;

    return 0;
}

### #1052
- [1052_貪婪的小偷 Part2](https://oj.lidemy.com/problem/1052)

//使用二維vector建構DP表，解0/1背包問題
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int n, w, tmp;
	vector<int> v_w(1,-1), v_p(1,-1);//在index=0推入無效值，讓資料從index=1開始

	cin >> n >> w;
	vector<vector<int>> dp(n + 1, vector<int>(w + 1));//讓資料從i=1, j=1開始排列
	
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		v_w.push_back(tmp);
		cin >> tmp;
		v_p.push_back(tmp);
	}

	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= w; j++) {
			if (i == 0 || j == 0) {//將i=0跟j=0填滿0
				dp[i][j] = 0;
			}
			else if (j < v_w[i]) {
				dp[i][j] = dp[i - 1][j]; 
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v_w[i]] + v_p[i]);
			}
		}
	}
	cout << dp[n][w] << endl;

	return 0;
}

### #1053
- [1053_走迷宮](https://oj.lidemy.com/problem/1053)

//使用其他演算法很容易超時
#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// 定義無限大
const int INF = climits;

// 定義迷宮結構
struct Maze {
    int h; // 高度
    int w; // 寬度
    vector<vector<char>> grid; // 圖案
    vector<vector<int>> dist; // 距離

    // 建構函數
    Maze(int h, int w) {
        this->h = h;
        this->w = w;
        grid.resize(h, vector<char>(w));
        dist.resize(h, vector<int>(w, INF));
    }

    // 讀取迷宮圖案
    void readGrid() {
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> grid[i][j];
            }
        }
    }

    // 判斷是否在範圍內
    bool inRange(int x, int y) {
        return x >= 0 && x < h&& y >= 0 && y < w;
    }

    // Dijkstra算法
    void dijkstra() {
        // 定義方向陣列
        int dx[] = { 1, -1, 0, 0 };
        int dy[] = { 0, 0, 1, -1 };

        // 建立優先佇列（以距離排序）
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

        // 將起點加入佇列並設定距離為0
        pq.push({ 0, 0 });
        dist[0][0] = 0;

        while (!pq.empty()) {
            // 取出佇列頂端元素（距離最小）
            auto p = pq.top();
            pq.pop();
            int x = p.second / w;
            int y = p.second % w;

            // 如果已經訪問過，則跳過
            if (p.first > dist[x][y]) continue;

            // 遍歷四個方向
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];

                // 如果在範圍內且不是牆壁，且有更小的距離，則更新並加入佇列
                if (inRange(nx, ny) && grid[nx][ny] == '.' && dist[nx][ny] > dist[x][y] + 1) {
                    dist[nx][ny] = dist[x][y] + 1;
                    pq.push({ dist[nx][ny], nx * w + ny });
                }
            }
        }
        // 輸出終點的距離（如果沒有路徑則輸出-1）
        if (dist[h - 1][w - 1] == INF) {
            cout << -1 << endl;
        }
        else {
            cout << dist[h - 1][w - 1] << endl;
        }
    }
};

// 主函數
int main() {
    // 讀取迷宮的高度和寬度
    int h, w;
    cin >> h >> w;

    // 建立迷宮物件
    Maze maze(h, w);

    // 讀取迷宮圖案
    maze.readGrid();

    // 執行Dijkstra算法
    maze.dijkstra();

    return 0;
}

###### tags: `Else OJ` `C++`