소프티어

package org.example;

import java.util.*;

import java.io.*;

public class Main {

public static int[] dx = { 1, 0, -1, 0};

public static int[] dy = {0, 1, 0, -1};

static class Person {

public int x;

public int y;

public Person(int x, int y) {

this.x = x;

this.y = y;

}

}

public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

public static ArrayList<Person> list = new ArrayList<>();

public static int n;

public static int m;

public static int[][] arr = new int[25][25];

public static boolean[][][] check = new boolean[4][25][25];

public static int result = 0;

public static ArrayList<Person> people = new ArrayList<>();

public static void main(String[] agrs) throws IOException {

input();

solve();

output();

}

public static void solve() throws IOException {

check[0][people.get(0).x][people.get(0).y] = true;

int amount = arr[people.get(0).x][people.get(0).y];

arr[people.get(0).x][people.get(0).y] = 0;

dfs(people.get(0).x, people.get(0).y, amount, 0, 0);

}

public static void input() throws IOException {

StringTokenizer st = new StringTokenizer(br.readLine());

n = Integer.parseInt(st.nextToken());

m = Integer.parseInt(st.nextToken());

for(int i = 1; i <= n; i++){

st = new StringTokenizer(br.readLine());

for(int j = 1; j <= n; j++){

arr[i][j] = Integer.parseInt(st.nextToken());

}

}

for (int i = 0; i < m; i++) {

st = new StringTokenizer(br.readLine());

int x = Integer.parseInt(st.nextToken());

int y = Integer.parseInt(st.nextToken());

people.add(new Person(x, y));

}

}

public static void dfs(int x, int y, int amount, int dist, int count) throws IOException {

if (dist == 3) {

if (count >= m - 1) {

result = Math.max(amount, result);

return;

}

check[count+1][people.get(count + 1).x][people.get(count + 1).y] = true;

dfs(people.get(count + 1).x, people.get(count + 1).y, amount + arr[people.get(count + 1).x][people.get(count + 1).y], 0, count + 1);

result = Math.max(amount, result);

return;

}

for (int i = 0; i < 4; i++) {

int nx = x + dx[i];

int ny = y + dy[i];

if (nx >= 1 && nx <= n && ny >= 1 && ny <= n) {

if (check[count][nx][ny] == false) {

int temp = arr[nx][ny];

check[count][nx][ny] = true;

int nextAmount = amount + arr[nx][ny];

arr[nx][ny] = 0;

dfs(nx, ny, nextAmount, dist + 1, count);

arr[nx][ny] = temp;

check[count][nx][ny] = false;

}

}

}

}

public static void output() throws IOException {

bw.write(String.valueOf(result));

bw.flush();

}

}

테스트 케이스

2 2

20 26 

100 20

1 2

2 1

166