P1518 [USACO2.4]兩隻塔姆沃斯牛 The Tamworth Two

• 2022 年 1 月 22 日
• 筆記
• 演算法日記

// Problem: P1518 [USACO2.4]兩隻塔姆沃斯牛 The Tamworth Two
// Contest: Luogu
// URL: //www.luogu.com.cn/problem/P1518
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// User: Pannnn

#include <bits/stdc++.h>

using namespace std;

// 獲取圖資訊，保存牛和人的當前位置
// 讀入時判斷是否為字元F和C，使用單獨的坐標存儲人和牛的坐標，圖中將字元替換為.
void getGraph(char (*graph)[15], int &cowX, int &cowY, int &humX, int &humY) {
    for (int i = 1; i <= 10; ++i) {
        for (int j = 1; j <= 10; ++j) {
            cin >> graph[i][j];
            if (graph[i][j] == 'F') {
                cowX = i;
                cowY = j;
                graph[i][j] = '.';
            } else if (graph[i][j] == 'C') {
                humX = i;
                humY = j;
                graph[i][j] = '.';
            }
        }
    }
}

int getRes(char (*graph)[15], int cowX, int cowY, int humX, int humY) {
    // 四個方向對應的x與y的偏移量，初始時人與牛都在下標為0對應的方向上
    int directCow = 0, directHum = 0;
    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    /*
        判斷是否能夠相遇，可以在移動次數達到一定值時判定為無法相遇。
        另一種思路：設定一種狀態，如果這個狀態以前出現過，說明他們進入了循環，不能相遇。
        狀態包括：人和牛的各自坐標x和y以及他們各自的方向。
    */
    // 圖100個點，如果移動200次沒有追上就不會再追上
    for (int i = 1; i <= 200; ++i) {
        // 判斷牛當前前進方向的前一個點是否為障礙物
        // 是障礙物就改變其方向
        if (graph[cowX + dx[directCow]][cowY + dy[directCow]] == '*') {
            directCow = (directCow + 1) % 4;
        } else {
            // 否則牛向此方向前進
            cowX = cowX + dx[directCow];
            cowY = cowY + dy[directCow];
        }
        
        if (graph[humX + dx[directHum]][humY + dy[directHum]] == '*') {
            directHum = (directHum + 1) % 4;
        } else {
            humX = humX + dx[directHum];
            humY = humY + dy[directHum];
        }
        
        if (cowX == humX && cowY == humY) {
            return i;
        }
    }
    return 0;
}

int main() {
    char graph[15][15] = { 0 };
    // 圖從[1,1]開始，且以*填充空白，簡化越界判斷
    fill(&graph[0][0], &graph[0][0] + sizeof(graph), '*');
    
    int cowX = -1, cowY = -1;
    int humX = -1, humY = -1;
    getGraph(graph, cowX, cowY, humX, humY);
    
    int res = getRes(graph, cowX, cowY, humX, humY);
    cout << res << endl;
    return 0;
}