Codeforces #35 (div2) C "Fire Again"
問題:http://www.codeforces.com/contest/35/problem/C
プラクティス.
n×mの区画が与えられて,出火した座標が与えられるので,出火した座標からもっとも遠い区画のひとつの座標を求める.
本番ではSPOJのBITMAPの問題と同じだと思いコピペして貼りつけたらテストケース29でTLE.諦めて最初から書き直したけど全区画と出火位置を全部計算していっても十分間に合ったみたい.テストケース4は多分1*1が入力で,"0 0"を出力するとPEとなってた.
import java.io.*; import java.util.*; public class C_FireAgain { public static void main(String[] args) throws Exception { File in = new File("input.txt"), out = new File("output.txt"); Scanner s; PrintWriter pw; if (in.exists()) { s = new Scanner(in); pw = new PrintWriter(out); } else { s = new Scanner(System.in); pw = new PrintWriter(System.out); } int n = s.nextInt(), m = s.nextInt(); int k = s.nextInt(); List<int[]> list = new ArrayList<int[]>(); for (int t = 0; t < k; ++t) { list.add(new int[] { s.nextInt() - 1, s.nextInt() - 1 }); } int max = 0, mi = 1, mj = 1; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { int min = Integer.MAX_VALUE; for (int[] p : list) { min = Math.min(min, Math.abs(i - p[0]) + Math.abs(j - p[1])); } if (min > max) { max = Math.max(max, min); mi = i + 1; mj = j + 1; } } } pw.println(mi + " " + mj); pw.close(); } }