UVa118 - Mutant Flatworld Explorers (實作題)

題目大意：

我們命令機器人依照我們的指令在陸地上移動，如果機器人根據我們的指令跳入海裡時，那接下來的機器人會知道那邊是海，而不會執行我們的指令。

舉例：假如向前走會掉入海裡，那則不會執行命令

指令有向左轉與向右轉、往前走，一開始會給你地圖的右上角，之後就是每一個機器人與其需要執行的指令。

題目要求 由於是根據向量座標，於是往北走的座標則為 x,y+1 , 南(x,y-1) , 西(x-1,y) , 東(x+1,y)

分析

簡單的實作題，根據地圖的大小，以及其方向執行命令，然後我們透過 map 記住現在的機器人掉入海的方向與其 x,y 座標，如果接下來有其他機器人也碰到此情況就不執行指令，然後需要記住題目給定的座標方向QQ。(我沒看懂這座標方向浪費了一堆時間)。

需要記住的是只有向前走才會掉入海哩，所以轉向的指令都會被執行。

心得

嗚嗚，英文好難。

圖論搜尋的題目再給予向量座標時跟用二維陣列的表格差太多了，我習慣的北方是(x-1,y)，但她的卻是 (x,y+1)， 還有想太少XD，我漏想只有往前走在會掉入海裡，原本的程式碼只要轉向朝海就會被我不執行XDDD，太貼心了www。

題目程式碼

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 110
using namespace std;
map<pair<int,int>,int> mp_lost ;
int direct[4][2] = {{0,1},{-1,0},{0,-1},{1,0}} ;
int n , m ; // n,m is border and d is now direct
int sx , sy , tx , ty , d ; //start x , start y ,
string ins , str_d; //instruction
map<char,int> map_sd ;
map<int,string> back_sd ;

int in_grid(int x , int y , int d  ){
    if(x < 0 || x > n )
        return 0 ;
    if(y < 0 || y > m )
        return 0 ;
    return 1 ;
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
    freopen("out.txt" , "w" , stdout );
#endif // LOCAL
    cin >> n >> m ;
    map_sd['N'] = 0 ;
    map_sd['W'] = 1 ;
    map_sd['S'] = 2 ;
    map_sd['E'] = 3 ;
    back_sd[0] = "N";
    back_sd[1] = "W";
    back_sd[2] = "S";
    back_sd[3] = "E";
    while(cin >> sx >> sy >> str_d ){
        cin >> ins ;
        //cout << ins << '\n' ;
        d = map_sd[str_d[0]] ;
        int flag = 1;
        for(int i = 0 ; i < ins.length() ; i++){
            if(ins[i] == 'F'){
                tx = sx ;
                ty = sy ;
                sx += direct[d][0] ;
                sy += direct[d][1] ;
                pair<int,int> pa(tx,ty) ;
                if(in_grid(sx,sy,d) == 0){
                    if(mp_lost.count(pa)){ //indicate past robot fell
                        sx = tx ;
                        sy = ty ;
                        continue ;
                    }
                    cout << tx << ' ' << ty << ' ' << back_sd[d] << ' ' << "LOST" <<'\n';
                    mp_lost[pa] = 1 ;
                    flag = 0 ;
                    break ;
                }
            }
            if(ins[i] == 'L') //change direction
                d = (d+4+1) % 4 ;
            if(ins[i] == 'R') //change direction
                d = (d+4-1) % 4 ;
            //cout << "i is : " << sx << ' ' << sy << ' ' << back_sd[d] << '\n' ;
        }
        if(flag)
            cout << sx << ' ' << sy << ' ' << back_sd[d] <<'\n';
    }
    return 0;
}