Advertisement
Guest User

Untitled

a guest
Jun 25th, 2017
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.57 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. import com.sun.org.apache.regexp.internal.recompile;
  5.  
  6. public class Main {
  7.  
  8.     private static Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
  9.     private static boolean[][] reacheble;
  10.     private static final int SIZE = 1000;
  11.     private static final int CENTER = 500;
  12.    
  13.     public static void main(String[] args) {
  14.         for (int step = 0; step < 10; ++step) {
  15.             reacheble = new boolean[SIZE][SIZE];
  16.             System.out.println(brute(step));
  17.         }
  18.     }
  19.  
  20.     private static final int[] dx = { -1, 0, 1, 0 };
  21.     private static final int[] dy = { 0, 1, 0, -1 };
  22.     private static int brute(int step) {
  23.         int[][][] used = new int[SIZE][SIZE][4];
  24.         for (int[][] a : used) {
  25.             for (int[] b : a) {
  26.                 Arrays.fill(b, -1);
  27.             }
  28.         }
  29.         used[CENTER][CENTER][0] = step;
  30.         dfs(CENTER, CENTER, 0, step, used);
  31.         int res = 0;
  32.         for (boolean[] a : reacheble) {
  33.             for (boolean b : a) {
  34.                 if (b) {
  35.                     ++res;
  36.                 }
  37.             }
  38.         }
  39.         return res;
  40.     }
  41.    
  42.     private static void dfs(int x, int y, int d, int step, int[][][] used) {
  43.         reacheble[x][y] = true;
  44.         if (step - 1 >= 0 && used[x + dx[d]][y + dy[d]][d] < step - 1) {
  45.             used[x + dx[d]][y + dy[d]][d] = step - 1;
  46.             dfs(x + dx[d], y + dy[d], d, step - 1, used);
  47.         }
  48.        
  49.         if (step - 1 >= 0 && used[x][y][(d + 1) % 4] < step - 1) {
  50.             used[x][y][(d + 1) % 4] = step - 1;
  51.             dfs(x, y, (d + 1) % 4, step - 1, used);
  52.         }
  53.         if (step - 1 >= 0 && used[x][y][(d - 1 + 4) % 4] < step - 1) {
  54.             used[x][y][(d - 1 + 4) % 4] = step - 1;
  55.             dfs(x, y, (d - 1 + 4) % 4, step - 1, used);
  56.         }
  57.  
  58.     }
  59. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement