반응형
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class B15684 {
static int N, M, H;
static int MinValue;
static final int INF = 987654321;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
int[][] map = new int[H + 2][N * 2 + 1];
int a = 0, b = 0;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
map[a][2 * (b - 1) + 1] = 1;
map[a][2 * (b - 1) + 2] = 1;
map[a][2 * (b - 1) + 3] = 1;
}
// for (int i = 0; i <= H + 1; i++) {
// for (int j = 0; j < N * 2 + 1; j++) {
// }
// }
boolean check = false;
for (int i = 1; i < N; i++) {
if (i != WhereGo(2 * (i - 1) + 1, map)) {
check = true;
break;
}
}
if (!check) {
System.out.println(0);
} else {
MinValue = INF;
DFS(0, map,1);
if (MinValue != INF) {
System.out.println(MinValue);
} else {
System.out.println(-1);
}
}
}
public static void DFS(int cnt, int[][] map,int starty) {
if (cnt != 0) {
boolean check = false;
for (int i = 1; i < N; i++) {
if (i != WhereGo(2 * (i - 1) + 1, map)) {
check = true;
break;
}
}
if (!check) {
MinValue = Math.min(MinValue, cnt);
return;
}
}
if (MinValue == 1) return;
if (cnt == 3) return;
int[][] mymap;
for (int i = starty; i <= H; i++) {
for (int j = 1; j < N * 2 - 2; j += 2) {
if (map[i][j] == 0 && map[i][j + 2] == 0) {
mymap = new int[H + 2][N * 2 + 1];
for (int ci = 0; ci <= H + 1; ci++) {
System.arraycopy(map[ci], 0, mymap[ci], 0, map[ci].length);
}
mymap[i][j] = 1;
mymap[i][j + 1] = 1;
mymap[i][j + 2] = 1;
DFS(cnt + 1, mymap,i);
}
}
}
}
public static int WhereGo(int x, int[][] map) {
int y = 0;
while (true) {
if (y == H + 1) {
return (x - 1) / 2 + 1;
}
if (map[y][x] == 0) {
y++;
continue;
}
if (map[y][x] == 1) {
if (map[y][x + 1] == 1) {
x += 2;
y++;
continue;
} else {
x -= 2;
y++;
continue;
}
}
}
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
https://www.acmicpc.net/problem/15684
15684번: 사다리 조작
사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로
www.acmicpc.net
반응형
'언어 > JAVA' 카테고리의 다른 글
| java : ArrayList : subList, reverse (0) | 2020.05.13 |
|---|---|
| PS 용 baseCode(추가예정) (0) | 2020.03.07 |
| JAVA : 자바의 빠른 입출력 (0) | 2020.01.23 |
| JAVA : 2차원 ArrayList (0) | 2020.01.23 |
| JAVA : 객체배열을 다루기(2차원 객체,1차원 정렬) (0) | 2020.01.23 |
