Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- import com.sun.org.apache.regexp.internal.recompile;
- public class Main {
- private static Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
- private static boolean[][] reacheble;
- private static final int SIZE = 1000;
- private static final int CENTER = 500;
- public static void main(String[] args) {
- for (int step = 0; step < 10; ++step) {
- reacheble = new boolean[SIZE][SIZE];
- System.out.println(brute(step));
- }
- }
- private static final int[] dx = { -1, 0, 1, 0 };
- private static final int[] dy = { 0, 1, 0, -1 };
- private static int brute(int step) {
- int[][][] used = new int[SIZE][SIZE][4];
- for (int[][] a : used) {
- for (int[] b : a) {
- Arrays.fill(b, -1);
- }
- }
- used[CENTER][CENTER][0] = step;
- dfs(CENTER, CENTER, 0, step, used);
- int res = 0;
- for (boolean[] a : reacheble) {
- for (boolean b : a) {
- if (b) {
- ++res;
- }
- }
- }
- return res;
- }
- private static void dfs(int x, int y, int d, int step, int[][][] used) {
- reacheble[x][y] = true;
- if (step - 1 >= 0 && used[x + dx[d]][y + dy[d]][d] < step - 1) {
- used[x + dx[d]][y + dy[d]][d] = step - 1;
- dfs(x + dx[d], y + dy[d], d, step - 1, used);
- }
- if (step - 1 >= 0 && used[x][y][(d + 1) % 4] < step - 1) {
- used[x][y][(d + 1) % 4] = step - 1;
- dfs(x, y, (d + 1) % 4, step - 1, used);
- }
- if (step - 1 >= 0 && used[x][y][(d - 1 + 4) % 4] < step - 1) {
- used[x][y][(d - 1 + 4) % 4] = step - 1;
- dfs(x, y, (d - 1 + 4) % 4, step - 1, used);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement