---
tags: Coding
---
# 做過的題目
## c124: 00532 - Dungeon Master (bfs)
### 想法一(失敗)
用遞迴好像會變成dfs的方式，結果就tle了。

#include<bits/stdc++.h>
using namespace std;
int cnt=0;
int l,r,c;
int end_distance=0;
void bfs(vector<vector<vector<char>>>maze,vector<vector<vector<int>>>&d,int z,int y,int x){
    if(z>=0 && z<l && y>=0 && y<r && x>=0 && x<c){
        char now=maze[z][y][x];
        if(now=='#')return;
        if(now=='E'){
            end_distance=d[z][y][x];
            return;
        }
        if(z+1<l && maze[z+1][y][x]!='#' && d[z+1][y][x]==0){
            d[z+1][y][x]=d[z][y][x]+1;
            bfs(maze,d,z+1,y,x);
        }
        if(z>0 && maze[z-1][y][x]!='#' && d[z-1][y][x]==0){
            d[z-1][y][x]=d[z][y][x]+1;
            bfs(maze,d,z-1,y,x);
        }
        if(x<c-1 && d[z][y][x+1]==0){
            d[z][y][x+1]+=d[z][y][x]+1;
            bfs(maze,d,z,y,x+1);
        }
        if(y<r-1 && d[z][y+1][x]==0){
            d[z][y+1][x]+=d[z][y][x]+1;
            bfs(maze,d,z,y+1,x);
        }
        if(x>0 && d[z][y][x-1]==0){
            d[z][y][x-1]+=d[z][y][x]+1;
            bfs(maze,d,z,y,x-1);
        }
        if(y>0 && d[z][y-1][x]==0){
            d[z][y-1][x]+=d[z][y][x]+1;
            bfs(maze,d,z,y-1,x);
        }
    }
    return;
}

int main(){
    int sl,sr,sc;//start l,start r,start c
    while(cin>>l>>r>>c){
        if(l==0 && r==0 && c==0)break;
        vector<vector<vector<char>>>maze(l);
        vector<vector<vector<int>>>d(l);
        for(int i=0;i<l;i++){
            maze[i].resize(r);
            d[i].resize(r);
        }
        for(int i=0;i<l;i++){
            for(int j=0;j<r;j++){
                d[i][j].resize(c,0);
                for(int k=0;k<c;k++){
                    char a;
                    cin>>a;
                    maze[i][j].push_back(a);
                    if(a=='S'){
                        sl=i;
                        sr=j;
                        sc=k;
                    }
                }
            }
        }
        bfs(maze,d,sl,sr,sc);
        if(end_distance)cout<<"Escaped in "<<end_distance<<" minute(s)."<<endl;
        else cout<<"Trapped!"<<endl;
        end_distance=0;
    }
    return 0;
}

### 想法二
想法一改成用queue就可以先丟進去的座標最先被搜尋。

#include<bits/stdc++.h>
using namespace std;
int l,r,c;
int end_distance=0;
int sl,sr,sc;//start l,start r,start c
int el,er,ec;//end l,end r,end c

struct pos{
    int z,y,x;
};

void debug(vector<vector<vector<int>>>vec){
    for(auto i:vec){
        for(auto j:i){
            for(auto k:j)cout<<k;
            cout<<endl;
        }
        cout<<endl;
    }
    cout<<endl;
}

void bfs(vector<vector<vector<int>>>maze,vector<vector<vector<int>>>&d,vector<vector<vector<int>>>&color){
    queue<pos>q;
    pos p={sl,sr,sc};
    q.push(p);
    while(!q.empty()){
        pos now=q.front();
        int z=now.z , y=now.y , x=now.x;
        color[z][y][x]=1;
        pos obj;
        if(now.z==el && now.y==er && now.x==ec){
            end_distance=d[z][y][x];
            return;
        }
        if(x+1<c){
            if(maze[z][y][x+1]!=0 && color[z][y][x+1]==0 && x+1<c){
                obj=now;
                obj.x++;
                d[z][y][x+1]+=d[z][y][x]+1;
                color[z][y][x+1]=1;
                q.push(obj);
            }
        }
        if(x>0){
            if(maze[z][y][x-1]!=0 && color[z][y][x-1]==0){
                obj=now;
                obj.x--;
                d[z][y][x-1]+=d[z][y][x]+1;
                color[z][y][x-1]=1;
                q.push(obj);
            }
        }
        if(y+1<r){
            if(maze[z][y+1][x]!=0 && color[z][y+1][x]==0){
                obj=now;
                obj.y++;
                d[z][y+1][x]+=d[z][y][x]+1;
                color[z][y+1][x]=1;
                q.push(obj);
            }
        }
        if(y>0){
            if(maze[z][y-1][x]!=0 && color[z][y-1][x]==0){
                obj=now;
                obj.y--;
                d[z][y-1][x]+=d[z][y][x]+1;
                color[z][y-1][x]=1;
                q.push(obj);
            }
        }
        if(z+1<l){
            if(maze[z+1][y][x]!=0 && color[z+1][y][x]==0){
                obj=now;
                obj.z++;
                d[z+1][y][x]+=d[z][y][x]+1;
                color[z+1][y][x]=1;
                q.push(obj);
            }
        }
        if(z>0){
            if(maze[z-1][y][x]!=0 && color[z-1][y][x]==0){
                obj=now;
                obj.z--;
                d[z-1][y][x]+=d[z][y][x]+1;
                color[z-1][y][x]=1;
                q.push(obj);
            }
        }
        q.pop();
    }
    return;
}

int main(){
    while(cin>>l>>r>>c){ //l(z) r(y) c(x)
        if(l==0 && r==0 && c==0)break;
        vector<vector<vector<int>>>maze(l);
        vector<vector<vector<int>>>d(l);
        vector<vector<vector<int>>>color(l);
        for(int i=0;i<l;i++){
            maze[i].resize(r);
            d[i].resize(r);
            color[i].resize(r);
        }
        for(int i=0;i<l;i++){
            for(int j=0;j<r;j++){
                d[i][j].resize(c,0);
                color[i][j].resize(c,0);
                for(int k=0;k<c;k++){
                    char a;
                    cin>>a;
                    if(a=='S'){
                        sl=i;
                        sr=j;
                        sc=k;
                        maze[i][j].push_back(2);
                    }
                    if(a=='E'){
                        el=i;
                        er=j;
                        ec=k;
                        maze[i][j].push_back(3);
                    }
                    if(a=='.')maze[i][j].push_back(1);
                    if(a=='#')maze[i][j].push_back(0);
                }
            }
        }
        bfs(maze,d,color);
        if(end_distance)cout<<"Escaped in "<<end_distance<<" minute(s)."<<endl;
        else cout<<"Trapped!"<<endl;
        end_distance=0;
    }
    return 0;
}

## uva 11240
https://zerojudge.tw/ShowProblem?problemid=k217
求最大長度子序列
這題乍看要用dp解，但實則只要簡單判斷就好

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

int arr[500005];

signed main() {
    int n;
    cin >> n;
    while (n--) {
        int m, sum = 1;
        cin >> m;
        for (int i = 0; i < m; i++) {
            cin >> arr[i];
        }
        int flag = 1;
        for (int i = 1; i < m; i++) {
            if (flag == 1 && arr[i - 1] > arr[i]) {
                sum++;
                flag = 0;
            } else if (flag == 0 && arr[i - 1] < arr[i]) {
                sum++;
                flag = 1;
            }
        }
        cout << sum << endl;
    }

    return 0;
}