[Java] UVa 11586 Train Tracks

題目連結

題意:
測資一行為一組，包含若干個鐵軌(track)
每個鐵軌都以兩個英文字母表示( M 或 F )
代表鐵軌的兩端(稱作 connector)
可能是 Male(M) 或 Female(F)

只有 M 對 F 才能將兩個鐵軌相連

題目問每組測資的鐵軌能否彼此相連成一個圓圈循環(cycle)
若是，輸出 LOOP；否則輸出NO LOOP

例如: MF MF MF
第一個的 M 與第二個的 F 相連
第二個的 M 與第三個的 F 相連
第三個的 M 與第一個的 F 相連
可以形成 cycle

MM FF
同理，第一個的兩個 M 都可分別與第二個的 F 相連
可以形成 cycle

解法:
首先判斷
若只有一個鐵軌無法形成 cycle

接著，可以發現，不管有幾段鐵軌
要形成cycle的條件就是每個 M 都要跟 F相連
也就是 M 跟 F 的總數要相同即可
-----------------------
我以每行為單位讀取測資
先確定是否為單一鐵軌(若是，只會有2個字母，字串長度為2)

若否，直接逐一判斷字元
用一個變數，預設為 0
遇到 M 就 ++，遇到 F 就 --
如果 M F 數量相當
最後變數的值會維持 0 (加上與扣掉相同的值)
藉此判斷最終結果

程式(Java):

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int T = Integer.parseInt(sc.nextLine());
	while (T-- > 0) {
	int sum = 0;
	String str = sc.nextLine();
	if (str.length() == 2)
	System.out.println("NO LOOP");
	else {
	for (int i = 0; i < str.length(); i++)
	sum = str.charAt(i) == 'M' ? sum+1 : (str.charAt(i) == 'F' ? sum-1 : sum);
	if (sum == 0)
	System.out.println("LOOP");
	else
	System.out.println("NO LOOP");
	}
	}
	}
	}

view raw UVa11586.java hosted with ❤ by GitHub