# 110CP2

## Final

#include <iostream>
#include <cstdlib>
#include <utility>
#include <string>
#include <vector>
#include <queue>

using namespace std;
int Round, M, N;
char grid[20][20]={};

#define RIGHT 0
#define DOWN 1
#define UP 2
#define LEFT 3

int steps[4][2] = {
    {0,1},
    {1,0},
    {-1,0},
    {0,-1}
};

struct cell{
    int dir;
    int pts;
    int i;
    int j;
    int count;
};

struct cell cache[20][20] = {};
queue<struct cell> que;

bool valid(int x, int y){
    return (
        x >= 0 && x < M && y >=0 && y < N &&
        grid[x][y] != 'x' &&
        grid[x][y] != 'A' && grid[x][y] != 'B'
    );
}

int calculateScore(int currentScore, int i, int j) {
    char gettingObject = grid[i][j];
    switch (gettingObject) {
        case 'm':
            return currentScore + 1;
        case 'n':
            return currentScore - 1;
        case 's':
            return currentScore * 2;
        case 't':
            return currentScore / 2;
        case '.':
        case 'b':
        default:
            return currentScore;
    }
}

string defaultOutput(int dir) {
    switch (dir) {
        case UP:
            return "UP";
        case DOWN:
            return "DOWN";
        case LEFT:
            return "LEFT";
        case RIGHT:
            return "RIGHT";
    }
    return "FALSE";
}

string next_dir(int ci, int cj, int point) {
    struct cell u, d, l, r;
    u.i = ci + steps[2][0], u.j = cj + steps[2][1], u.dir = UP, u.count = 1;
    d.i = ci + steps[1][0], d.j = cj+ steps[1][1], d.dir = DOWN, d.count = 1;
    l.i = ci + steps[3][0], l.j = cj + steps[3][1], l.dir = LEFT, l.count = 1;
    r.i = ci + steps[0][0], r.j = cj + steps[0][1], r.dir = RIGHT, r.count = 1;
    if (valid(l.i, l.j)) {
        l.pts = calculateScore(point, l.i, l.j);
        que.push(l);
    }
    if (valid(r.i, r.j)) {
        r.pts = calculateScore(point, r.i, r.j);
        que.push(r);
    }
    if (valid(u.i, u.j)) {
        u.pts = calculateScore(point, u.i, u.j);
        que.push(u);
    }
    if (valid(d.i, d.j)) {
        d.pts = calculateScore(point, d.i, d.j);
        que.push(d);
    }
    while(!que.empty()){
        struct cell deq = que.front();
        que.pop();
        if(cache[deq.i][deq.j].pts < deq.pts)
            cache[deq.i][deq.j] = deq;  
        if(deq.count < 5) {
            for(int i = 0; i < 4; i++){
                int next_i =  deq.i+steps[i][0];
                int next_j = deq.j+steps[i][1];
                if(valid(next_i, next_j)) {
                    struct cell next;
                    next.dir = deq.dir;
                    next.count = deq.count+1;
                    next.i = next_i;
                    next.j = next_j;
                    que.push(next);
                }
            }
        }
    }
    int max = 0;
    int max_dir;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(cache[i][j].pts > max){
                max = cache[i][j].pts;
                max_dir = cache[i][j].dir;
            }
        }
    }
    return defaultOutput(max_dir);
}

// cahce[i][j] = max point can be reached within 3 steps


int main(void){
    int A, B;
    char me;
    int ai, aj, bi, bj;
    cin >> Round >> M >> N;
    for(int i=0;i<M;i++)
        for(int j=0;j<N;j++) {
            cin >> grid[i][j];
            if(grid[i][j] == 'A')
                ai = i, aj = j;
            else if(grid[i][j] == 'B')
                bi = i, bj = j;
        }

    cin >> A >> B >> me;
    if(me == 'A')
        cout << next_dir(ai, aj, A) << endl;
    else
        cout << next_dir(bi, bj, B) << endl;
}

## Cat

#### solution1: without malloc

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int steps[4][2] = {
    {0,1},
    {1,0},
    {0,-1},
    {-1,0}
};

typedef struct cell {
    int x;
    int y;
    int count;
} cell;

void enqueue(cell queue[1000000], cell elem, int* rear) {
    queue[*rear] = elem;
    (*rear)++;
}

cell dequeue(cell queue[1000000], int* front) {
    (*front)++;
    return queue[*front-1];
}

int bfs(char grid[100][100], int n) {
    cell queue[1000000];
    int front = 0, rear = 1;
    cell start;

    // find start point
    for(int i = 0; i < n; i++)
        for(int j = 0; grid[i][j] != 0; j++)
            if(grid[i][j] == 'K') {
                    start.x = i;
                    start.y = j;
                    start.count = 0;
                    break;
            }
    
    queue[0] = start;
    while(front != rear) {
        cell deq = dequeue(queue, &front);
        int x = deq.x, y = deq.y;
        grid[x][y] = '#';
        for(int i = 0; i < 4; i++) {
            int nextX = x + steps[i][0];
            int nextY = y + steps[i][1];
            if(nextX >= 0 && nextX < 100 && nextY >= 0 && nextY <100) {
                if(grid[nextX][nextY] == '.') {    
                    cell next = (cell){nextX, nextY, deq.count+1};
                    enqueue(queue, next,  &rear);
                } else if (grid[nextX][nextY] == '@')
                    return deq.count+1; 
            }
        }
    }
    return 0;
}

int main() {
    int n;
    while(scanf("%d", &n) && n > 0) {
        char grid[100][100] = {'0'};
        for(int i = 0; i < n; i++)
            scanf("%s", grid[i]);
        int res = bfs(grid, n);
        if(res)
            printf("%d\n", res);
        else
            printf("= =\"\n");
    }
    return 0;
}

#### solution2: with malloc

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int steps[4][2] = {
    {0,1},
    {1,0},
    {0,-1},
    {-1,0}
};

typedef struct cell {
    int x;
    int y;
    int count;
} cell;

void enqueue(cell** queue, cell* elem, int* rear) {
    queue[*rear] = elem;
    (*rear)++;
}

cell* dequeue(cell** queue, int* front) {
    (*front)++;
    return queue[*front-1];
}

int bfs(char grid[101][101], int n) {
    cell* queue[1000000];
    int front = 0, rear = 1;
    cell* start = (cell*)malloc(sizeof(cell));

    // find start point
    for(int i = 0; i < n; i++) {
        for(int j = 0; grid[i][j] < 100; j++) {
            if(grid[i][j] == 'K') {
                    start->x = i;
                    start->y = j;
                    start->count = 0;
            }
        }
    }
    queue[0] = start;


    while(front != rear) {
        cell* deq = dequeue(queue, &front);
        int x = deq->x, y = deq->y;
        grid[x][y] = '#';
        for(int i = 0; i < 4; i++) {
            int nextX = x + steps[i][0];
            int nextY = y + steps[i][1];
            if(nextX >= 0 && nextX < 100 && nextY >= 0 && nextY <100) {
                if(grid[nextX][nextY] == '.') {    
                    cell* next = (cell*)malloc(sizeof(cell));
                    next->x = nextX;
                    next->y = nextY;
                    next->count = deq->count+1;
                    enqueue(queue, next,  &rear);
                } else if (grid[nextX][nextY] == '@') {
                    int res = deq->count+1;
                    while(front != rear)
                        free(dequeue(queue, &front));
                    free(deq);
                    return res;
                }
                    
            }
        }
        free(deq);
    }
    return 0;
}

int main() {
    int n;
    while(scanf("%d", &n) && n > 0) {
        char grid[101][101] = {'#'};
        for(int i = 0; i < n; i++) {
            scanf("%s", grid[i]);
        }
        int res = bfs(grid, n);
        if(res)
            printf("%d\n", res);
        else
            printf("= =\"\n");
    }
    return 0;
}

## [LIS](https://leetcode.com/problems/longest-increasing-subsequence/)

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

解法一：`n^2`
建立一個dp array，`dp[i]`代表的是以`nums[i]`做為結尾的seq的最大長度，做法是搜尋 `dp[0]` ~ `dp[i-1]`，比對相對應的nums然後更新`dp[i]`。

int lengthOfLIS(int* nums, int numsSize){
    int dp[numsSize];
    int max = 1;
    for(int i = 0; i < numsSize; i++) {
        dp[i] = 1;
        for(int j = 0; j < i; j++)
            dp[i] = (nums[i]>nums[j] && dp[i] <= dp[j]) ? dp[j]+1: dp[i];
        max = dp[i]>max ? dp[i] : max;
    }
    return max;
}

解法二: `nlogn`
建立一個dp array，`dp[i]`代表的是長度i的最佳結尾，關於最佳結尾，可以思考 `1,2,3` 和 `1,2,5`誰對於這個題目來說更有未來，肯定是前者吧因為之後出現`4`後者的長度不會再增加了，前者卻可以變成`1,2,3,4`。每個新插入的數只有兩種可能
* 如果比目前`dp[-1]`（最後一個）大，可以直接串上, e.g., `1,2,3`--插入4-->`1,2,3,4`
* 如果比`dp[-1]`小，就用bs更新dp， e.g., `1,2,5`--插入4-->`1,2,4`

搜尋的部分參考[這題](https://leetcode.com/problems/search-insert-position/)，上課講過。最後回傳dp長度即可

int lengthOfLIS(int* nums, int numsSize){
    int dp[numsSize];
    int idx = 0;
    for(int i = 0; i < numsSize; i++) {
        if(!idx || (dp[idx-1] < nums[i])) {
            dp[idx] = nums[i];
            idx++;
        } else {
            int l = 0, r = idx-1; 
            while(l <= r) {
                int mid = (l+r) >> 1;
                if(dp[mid] >= nums[i])
                    r = mid-1;
                else
                    l = mid+1;
            }
            dp[l] = nums[i];
        }
    }
    return idx;
}

## [minimum-number-of-removals-to-make-mountain-array](https://leetcode.com/problems/minimum-number-of-removals-to-make-mountain-array/)

* 移除最少數字=計算最大長度
* 以`nums[i]`為山頂的mountain array，最大長度是LIS(`nums[:i+1]`)+LIS(`nums[i:]`)-1

int minimumMountainRemovals(int* nums, int numsSize){
    int nums_r[numsSize]; // copy and reverse from nums
    for(int i = 0; i < numsSize; i++)
        nums_r[i] = nums[numsSize-i-1];
    
    int l2r[numsSize], r2l[numsSize];
    LIS(nums, l2r, numsSize); // left to right
    LIS(nums_r, r2l, numsSize);

    int max = 0;
    for(int i = 0; i < numsSize; i++)
        if(l2r[i]>=2 && r2l[numsSize-i-1]>=2)
            max = l2r[i]+r2l[numsSize-i-1]-1 > max ? l2r[i]+r2l[numsSize-i-1]-1 : max;
    return numsSize-max;
}

void LIS(int* nums, int* maxLens, int numsSize){
    int dp[numsSize];
    int idx = 0;
    for(int i = 0; i < numsSize; i++) {
        if(!idx || (dp[idx-1] < nums[i])) {
            dp[idx] = nums[i];
            idx++;
        } else {
            int l = 0, r = idx-1;
            while(l <= r) {
                int mid = (l+r) >> 1;
                if(dp[mid] >= nums[i])
                    r = mid-1;
                else
                    l = mid+1;
            }
            dp[l] = nums[i];
        }
        maxLens[i] = idx;
    }
}