A Knight's Journey--POJ 2488
32172 단어 poj
2. 주의사항: 기사가 점프하는 순서(알파벳 작성 순서 주의), DFS에서 귀속 주의는 입구의 수를 제어한다.
3. 실현 방법:
1
#include
<
iostream
>
2
using
namespace
std;
3
4
int
dir[
8
][
2
]
=
{
5
{
-
1
,
-
2
},{
1
,
-
2
},{
-
2
,
-
1
},{
2
,
-
1
},
6
{
-
2
,
1
},{
2
,
1
},{
-
1
,
2
},{
1
,
2
}
7
};
8
struct
Node
9
{
10
int
x,y;
11
bool
Exite;
12
};
13
Node loc[
27
];
14
int
x,y,step,map[
27
][
27
];
15
bool
mark;
16
17
bool
Judge(
int
pos_x,
int
pos_y)
18
{
19
if
(pos_x
>
x
||
pos_x
<
1
||
pos_y
>
y
||
pos_y
<
1
)
20
return
false
;
21
if
(map[pos_x][pos_y])
22
return
false
;
23
return
true
;
24
}
25
26
void
DFS(
int
pos_x,
int
pos_y)
27
{
28
if
(
!
mark)
29
{
30
for
(
int
i
=
0
;i
<
8
;i
++
)
31
{
32
if
(Judge(pos_x
+
dir[i][
0
],pos_y
+
dir[i][
1
]))
33
{
34
if
(step
==
x
*
y
-
1
)
35
{
36
mark
=
1
;
37
step
++
;
38
map[pos_x
+
dir[i][
0
]][pos_y
+
dir[i][
1
]]
=
1
;
39
loc[step].x
=
pos_x
+
dir[i][
0
];
40
loc[step].y
=
pos_y
+
dir[i][
1
];
41
break
;
42
}
43
if
(mark
==
1
)
44
return
;
45
step
++
;
46
map[pos_x
+
dir[i][
0
]][pos_y
+
dir[i][
1
]]
=
1
;
47
loc[step].x
=
pos_x
+
dir[i][
0
];
48
loc[step].y
=
pos_y
+
dir[i][
1
];
49
DFS(pos_x
+
dir[i][
0
],pos_y
+
dir[i][
1
]);
50
step
--
;
51
map[pos_x
+
dir[i][
0
]][pos_y
+
dir[i][
1
]]
=
0
;
52
}
53
}
54
}
55
}
56
57
int
main()
58
{
59
int
n,i
=
0
,flag;
60
cin
>>
n;
61
while
(n
--
)
62
{
63
cin
>>
x
>>
y;
64
step
=
0
;
65
memset(map,
0
,
sizeof
(map));
66
memset(loc,
0
,
sizeof
(loc));
67
cout
<<
"
Scenario #
"
<<++
i
<<
"
:
"
<<
endl;
68
flag
=
0
;
69
for
(
int
p
=
1
;p
<=
x;p
++
)
70
{
71
for
(
int
q
=
1
;q
<=
y;q
++
)
72
{
73
if
(
!
flag)
74
{
75
step
=
1
;
76
mark
=
0
;
77
memset(map,
0
,
sizeof
(map));
78
memset(loc,
0
,
sizeof
(loc));
79
map[p][q]
=
1
;
80
loc[step].x
=
p;
81
loc[step].y
=
q;
82
DFS(p,q);
83
if
(x
*
y
==
1
)
84
mark
=
1
;
85
if
(mark)
86
{
87
for
(
int
j
=
1
;j
<=
x
*
y;j
++
)
88
{
89
cout
<<
char
(loc[j].y
+
'
A
'
-
1
)
<<
char
(loc[j].x
+
'
0
'
);
90
}
91
if
(n
==
0
)
92
cout
<<
endl;
93
else
94
cout
<<
endl
<<
endl;
95
flag
=
1
;
96
}
97
}
98
99
}
100
}
101
if
(
!
flag)
102
{
103
if
(n
==
0
)
104
cout
<<
"
impossible
"
<<
endl;
105
else
106
cout
<<
"
impossible
"
<<
endl
<<
endl;
107
}
108
}
109
return
0
;
110
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3071: Football(확률 DP)Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
