UVa11831 - Sticker Collector Robot(DFS)

題目大意

給你一個地圖，地圖中有貼紙與柱子，機器人碰到柱子則無法前進，碰到貼紙則會蒐集貼紙
給你機器人的位置，並告訴你機器人的行動方式，請告訴機器人可以蒐集幾個貼紙。

機器人會向左轉、向右轉、往前走三個動作，並告訴妳一開始機器人面對的方位是哪邊。

題目連結

重點觀念

• 模擬操作

分析

• 由於機器人只有東西南北四個方位，而每個方位都有一個左邊、一個右邊，因此我們可以直接將各種情況列舉出來，下面舉例
  • 北方的左邊是西邊
  • 北方的右邊是東邊
• 用一個 visit 來表示地圖中的這個 cell 有沒有被走過，如果有且這個 cell 有貼紙則答案 +1。
• 將邊界更輕鬆處理，在第 0 層與 \(n+1\) 層的 cell 全部都設定為牆壁的

參考連結

UVa 11831 - Sticker Collector Robot by 小白菜又菜

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 120
using namespace std;
int n, m, s;
int x, y, ans;
int visit[MAXN][MAXN]; //判斷是不是第一次經過此 cell，避免撞牆後重複蒐集地圖
string graph[MAXN]; //地圖
string line, direct, pillars; //direct 機器人的方位, pillars 表示 row 都是柱子(邊界)
map<string, string> L; //L[方位A] = 方位B，方位 A 的左邊是方位 B
map<string, string> R; //與上面概念向通

void walk(char cmd){
    int flag = 0;
    if(cmd == 'F'){ //如果是往前走
        //如果往此方向走，並且不撞到支柱，就讓機器人往那邊走
        if(direct == "N" && graph[x-1][y] != '#') x = x-1;
        if(direct == "S" && graph[x+1][y] != '#') x = x+1;
        if(direct == "O" && graph[x][y-1] != '#') y = y-1;
        if(direct == "L" && graph[x][y+1] != '#') y = y+1;
        if(!visit[x][y] && graph[x][y] == '*') ans++; //如果第一次走到且此 cell 有貼紙則答案+1
        visit[x][y] = 1; //表示並不是第一次經過
    }
    else if(cmd == 'D') direct = R[direct]; //轉向
    else if(cmd == 'E') direct = L[direct];
    //cout << "cmd x y graph " << cmd << " " << x << " " << y << " " << direct << "\n";
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL

    L["N"] = "O"; L["O"] = "S"; L["S"] = "L", L["L"] = "N"; //將各種方位轉向都列舉出來
    R["N"] = "L"; R["L"] = "S"; R["S"] = "O", R["O"] = "N";

    while(cin >> n >> m >> s && (n+m+s) != 0){
        memset(visit, 0, sizeof(visit));
        pillars = "";
        for(int i = 0; i <= m+1; i++) pillars += "#"; //建造邊界牆

        graph[0] = pillars; //分析第三點
        for(int i = 1; i <= n; i++){
            cin >> line;
            graph[i] = "#" + line + "#"; //最左邊、最右邊都加入支柱，避免邊界額外判斷
            for(int j = 1; j <= m; j++){
                if(graph[i][j] == 'N' || graph[i][j] == 'S' || graph[i][j] == 'L' || graph[i][j] == 'O'){ //找到機器人現在方位，並且定位
                    x = i;
                    y = j;
                    direct = graph[i][j];
                }
            }
        }
        graph[n+1] = pillars; //分析第三點

        ans = 0;
        cin >> line;
        for(int i = 0; i < line.length(); i++){ //執行機器人全部指令
            walk(line[i]);
        }
        cout << ans << "\n"; //輸出答案
    }
    return 0;
}