[Java] UVa 12405 Scarecrow

題目連結

題意:
有一塊 1 * N 的田
.  表示作物可生長的空地
# 是不可用的
稻草人可以立在任何地方
可照顧它所在與左右各 1 塊的區域
求最少要立多少稻草人
才能保護所有作物可生長空地

解法:
既然所有 . 空地都要被保護
就線性掃過整塊田
遇到 . 就算一隻

而且一隻可以照顧三格
立完後往後跳 3 格繼續掃描即可

程式(Java):

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int T = Integer.valueOf(sc.nextLine());
	for (int i = 1; i <= T; i++) {
	int N = Integer.valueOf(sc.nextLine());
	int num = 0;
	String f = sc.nextLine();
	for (int j = 0; j < N; j++) {
	if (f.charAt(j) == '.') {
	num++;
	j += 2;
	}
	}
	System.out.println("Case " + i + ": " + num);
	}
	}
	}

view raw UVa12405.java hosted with ❤ by GitHub