---
# System prepended metadata

title: Mutant Flatworld Explorers(UVA118)
tags: [CPE一顆星必考題]

---

# Mutant Flatworld Explorers(UVA118)
## [程式繳交區](https://hackmd.io/@Renektonn/BJwTgeytkg/edit)
## 題目
[點我](https://onlinejudge.org/external/1/118.pdf)

## 解題系統
[UVA](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=54)
[ZJ](https://zerojudge.tw/ShowProblem?problemid=c082)

## 演算法
```
1.  輸入右上角頂點座標maxX, maxY
2.  定義一個布林陣列isLost[0~maxX][0~maxY]={},再定義方向陣列dy,dx(北東南西)
3.  輸入posX,posY,dir(將dir轉為數字)，若無法，則停止
4.  輸入ins，定義flag = 1 
5.  掃過ins，對於每一個c=ins[i]，判斷它是'L','R','F'哪個
        若是'L'，dir=dir - 1，若dir<0，dir += 4
        若是'R'，dir=dir + 1，若dir>=4，dir-=4
        若是'F'
            如果移動後會掉下去
                如果當前位置已經有人掉下去過
                    跳過
                否則
                    在當前位置做標記
                    輸出posX posY dir(轉回真正的方向) LOST
                    flag = 0
                    break
            否則
                移動
6.  若flag=1，輸出posX posY dir(轉回真正的方向)
```

## 程式碼
```cpp=
#include <bits/stdc++.h>
#define int long long int
using namespace std;
int maxX, maxY;

int isValid (int x, int y) {
    return 0 <= x and x <= maxX and 0 <= y and y <= maxY;
}
 
signed main() {
    cin >> maxX >> maxY;
    bool isLost[51][51] = {};
    int dy[4] = {1, 0, -1, 0};
    int dx[4] = {0, 1, 0, -1};
    char tmp;
    int posX, posY, dir;
    while (cin >> posX >> posY >> tmp) {
        if (tmp == 'N') dir = 0;
        else if (tmp == 'E') dir = 1;
        else if (tmp == 'S') dir = 2;
        else if (tmp == 'W') dir = 3;
        string ins;
        cin >> ins;
        int flag = 1;
        for (int i = 0; i < ins.length(); i++) {
            char c = ins[i];
            if (c == 'L') {
                dir = dir - 1;
                if (dir < 0) dir += 4;
            } else if (c == 'R') {
                dir = dir + 1;
                if (dir >= 4) dir -= 4;
            } else if (c == 'F') {
                int nextX = posX + dx[dir], nextY = posY + dy[dir];
                if (!isValid(nextX, nextY)) {
                    if (!isLost[posX][posY]) {
                        isLost[posX][posY] = 1;
                        cout << posX << " " << posY << " ";
                        if (dir == 0) cout << "N";
                        else if (dir == 1) cout << "E";
                        else if (dir == 2) cout << "S";
                        else if (dir == 3) cout << "W";
                        cout << " LOST" << endl;
                        flag = 0;
                        break;
                    }
                } else {
                    posX = nextX;
                    posY = nextY;
                }
            }
        }
        if (flag) {
            cout << posX << " " << posY << " ";
            if (dir == 0) cout << "N";
            else if (dir == 1) cout << "E";
            else if (dir == 2) cout << "S";
            else if (dir == 3) cout << "W";
            cout << endl;
        }
    }
    
    return 0;
}
```

## 以前寫的程式碼
```cpp=
#include <bits/stdc++.h>
using namespace std;

int boundX , boundY;

int dx[] = {0 , 1 , 0 , -1};
int dy[] = {1 , 0 , -1 , 0};
vector <pair<int , int>> v;

bool outBound(int x , int y){
    return x > boundX || x < 0 || y > boundY || y < 0;
}

int getDir(int d){
    if(d == 'N') return 0;
    if(d == 'E') return 1;
    if(d == 'S') return 2;
    if(d == 'W') return 3;
    
    if(d == 0) return 'N';
    if(d == 1) return 'E';
    if(d == 2) return 'S';
    return 'W';
}

void output(int x , int y , int dir , int flag){
    dir = getDir(dir);
    if(flag){
        cout << x << " " << y << " " << (char) dir << " LOST\n";
    }
    else{
        cout << x << " " << y << " " << (char) dir << "\n";
    }
}

bool isOff(int x , int y){
    for(int i = 0 ; i < v.size() ; i++){
        if(x == v[i].first && y == v[i].second){
            return 1;
        }
    }
    return 0;
}

bool move(int &x , int &y , int dir){
    if(outBound(x + dx[dir] , y + dy[dir])){
        if(isOff(x , y)) return 0;
        v.push_back(make_pair(x , y));
        return 1;
    }
    x += dx[dir];
    y += dy[dir];
    return 0;
}

void turnLeft(int &dir){
    dir = (dir + 3) % 4;
}

void turnRight(int &dir){
    dir = (dir + 1) % 4;
}

int main(){
    cin >> boundX >> boundY;
    int x , y;
    char d;
    string ins;
    while(cin >> x >> y >> d >> ins){
        int dir = getDir(d);
        int flag;
        for(int i = 0 ; i < ins.length() ; i++){
            if(ins.at(i) == 'F'){
                flag = move(x , y , dir);
                if(flag == 1) break;
            } else if(ins.at(i) == 'L'){
                turnLeft(dir);
            } else if(ins.at(i) == 'R'){
                turnRight(dir);
            }
        }
        output(x , y , dir , flag);
    }

    return 0;
}

```

## 我犯的錯

要仔細看題目
最好多用function

