Submission #169666

---

Source Code Expand

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigInteger;
 
import java.util.*;
import java.util.Map.Entry;
 
public class Main {
	
	public static final int[][] move_dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	
	public static boolean is_ok(int x, int y, final int sx, final int sy, int ex, int ey){
		if(x < sx || y < sy || x > ex || y > ey){
			return false;
		}else{
			return true;
		}
	}
	
	public static long dfs(final int deep, final int N, final int sx, final int sy, final int ex, final int ey, LinkedList<Integer> nums, boolean[] using, int[] xs, int[] ys){
		LinkedList<Integer> nexts = new LinkedList<Integer>(nums);
		for(Iterator<Integer> iter = nexts.iterator(); iter.hasNext(); ){
			final int next = iter.next();
			final int x = xs[next];
			final int y = ys[next];
			
			if(!is_ok(x, y, sx, sy, ex, ey)){
				iter.remove();
			}
		}
		
		long max = 0;
		
		for(int next : nexts){
			final int x = xs[next];
			final int y = ys[next];
			
			using[next] = true;
			final long current = (ex - sx + 1) + (ey - sy + 1) - 1;
			//System.out.println(current + " " + sx + " " + sy + " " + ex + " " + ey + " " + x + " " + y);
			
			long ret = 0;
			
			if(sx <= x - 1 && sy <= y - 1){
				ret += dfs(deep + 1, N,    sx,    sy, x - 1, y - 1, nexts, using, xs, ys);
			}
			if(x + 1 <= ex && sy <= y - 1){
				ret += dfs(deep + 1, N, x + 1,    sy,    ex, y - 1, nexts, using, xs, ys);
			}
			if(sx <= x + 1 && y + 1 <= ey){
				ret += dfs(deep + 1, N,    sx, y + 1, x - 1,    ey, nexts, using, xs, ys);
			}
			if(x + 1 <= ex && y + 1 <= ey){
				ret += dfs(deep + 1, N, x + 1, y + 1,    ex,    ey, nexts, using, xs, ys);
			}
			
			max = Math.max(max, current + ret);
			
			using[next] = false;
		}
		
		//System.out.println(deep + " " + max);
		return max;
	}
	
	public static void main(String[] args) throws IOException{
		Scanner sc = new Scanner(System.in);
		
		final int W = sc.nextInt();
		final int H = sc.nextInt();
		
		final int N = sc.nextInt();
		
		int[] xs = new int[N];
		int[] ys = new int[N];
		LinkedList<Integer> nexts = new LinkedList<Integer>();
		for(int i = 0; i < N; i++){
			xs[i] = sc.nextInt() - 1;
			ys[i] = sc.nextInt() - 1;
			nexts.add(i);
		}
		
		System.out.println(dfs(0, N, 0, 0, W - 1, H - 1, nexts, new boolean[N], xs, ys));
	}
	
	public static class Scanner {
		
		private BufferedReader br;
		private StringTokenizer tok;
		
		public Scanner(InputStream is) throws IOException{
			br = new BufferedReader(new InputStreamReader(is));
			getLine();
		}
		
		private void getLine() throws IOException{
			while(tok == null || !tok.hasMoreTokens()){
				tok = new StringTokenizer(br.readLine());
			}
		}
		
		private boolean hasNext(){
			return tok.hasMoreTokens();
		}
		
		public String next() throws IOException{
			if(hasNext()){
				return tok.nextToken();
			}else{
				getLine();
				return tok.nextToken();
			}
		}
		
		public int nextInt() throws IOException{
			if(hasNext()){
				return Integer.parseInt(tok.nextToken());
			}else{
				getLine();
				return Integer.parseInt(tok.nextToken());
			}
		}
		
		public long nextLong() throws IOException{
			if(hasNext()){
				return Long.parseLong(tok.nextToken());
			}else{
				getLine();
				return Long.parseLong(tok.nextToken());
			}
		}
		
		public double nextDouble() throws IOException{
			if(hasNext()){
				return Double.parseDouble(tok.nextToken());
			}else{
				getLine();
				return Double.parseDouble(tok.nextToken());
			}
		}
	}
}

Submission Info

Judge Result