1
/*
2
* ZJU2411.cpp
3
*
4
* Created on: 2011-3-27
5
* Author: Administrator
6
*
7
* 题目分析：
8
* 1. 异点同色之间才能消去
9
* 2. 可以走界外
10
*
11
* 算法分析：
12
* 1. 从一点出发向某个方向扩展直到不能再扩展，其他3个方向相同处理
13
* 2. 如从某一点a出发扩展，若a点方向是0，那么接下去0和2方向不需要再扩展，因为父节点已经扩展过了
14
* 3. 扩展是先入队，不标记，等出队时候再标记，因为存在以下可能：
15
* 棋板如下：
16
* 1)2)
17
* 1)红 空
18
* 2)空 空
19
* 3)蓝 红
20
* 搜索的方向次序是0（下），1（右），2（上），3（左）
21
* 搜索的转次是1
22
* 搜索的点是(1,1) -> (3, 2)
23
* (1, 1)扩展出(2, 1), (1, 2)
24
* (2, 1)扩展出(2, 2)
25
* 假设已经标记，那么(1, 1) -> (1, 2) -> (2, 2) -> (3, 2)这条途径将被(1, 1) -> (2, 1) -> (2, 2)埋没
26
*/
27
28
#include
<
stdio.h
>
29
#include
<
stdlib.h
>
30
#include
<
memory.h
>
31
#include
<
queue
>
32
33
using
namespace
std;
34
35
const
int
MAXN
=
100
+
2
;
36
37
struct
Status {
38
int
m_x, m_y, m_c, m_d;
//
行，列，转次，方向
39
Status(
int
x,
int
y,
int
c,
int
d) : m_x(x), m_y(y), m_c(c), m_d(d) {}
40
};
41
42
int
g_dir[
4
][
2
]
=
{
43
{
1
,
0
},
//
下
44
{
0
,
1
},
//
右
45
{
-
1
,
0
},
//
上
46
{
0
,
-
1
}
//
左
47
};
48
49
//
输入输出以及数组类型均定义为全局变量，命名规则，g_变量名，g_ans，g_数组名
50
int
g_maze[MAXN][MAXN], g_maze_tmp[MAXN][MAXN];
51
52
int
g_N, g_M;
53
int
g_x1, g_y1, g_x2, g_y2;
54
int
g_T;
55
int
g_ans;
56
57
//
是否当前方向与扩展方向是否在一条线上
58
inline
bool
is_linable(
int
orig_dir,
int
next_dir) {
59
//
如果是初始点
60
if
(orig_dir
==
-
1
)
61
return
false
;
//
那么非线性
62
63
//
如果是同向有反向
64
if
(orig_dir
==
next_dir
||
2
==
abs(orig_dir
-
next_dir))
65
return
true
;
//
那么线性
66
67
return
false
;
//
否则非线性
68
}
69
70
//
是否下一个点可以到达
71
inline
bool
is_reachable(
int
x,
int
y) {
//
(x, y)是否可达
72
//
下个位置可行，可以到达界外
73
if
(x
>=
0
&&
x
<=
g_N
+
1
&&
y
>=
0
&&
y
<=
g_M
+
1
&&
0
==
g_maze_tmp[x][y])
74
return
true
;
75
76
return
false
;
//
不可达
77
}
78
79
//
是否已经达到目标点
80
inline
bool
is_arrived(
int
x,
int
y) {
81
if
(x
==
g_x2
&&
y
==
g_y2)
82
return
true
;
83
84
return
false
;
//
否
85
}
86
87
//
单纯的从(g_x1, g_y1) 搜索到一条2折内到(g_x2, g_y2)的路径
88
bool
special_bfs() {
89
memcpy(g_maze_tmp, g_maze,
sizeof
(g_maze));
90
91
//
首先可以确定的是若是两次点击同一个点，虽然相同但是不能消去
92
queue
<
Status
>
q;
93
q.push(Status(g_x1, g_y1,
-
1
,
-
1
));
94
95
while
(
!
q.empty()) {
96
Status t
=
q.front();
97
q.pop();
98
g_maze_tmp[t.m_x][t.m_y]
=
-
1
;
//
标记为不可达
99
100
for
(
int
i
=
0
; i
<
4
; i
++
) {
//
四个方向扩展，
101
//
如果同向或者相向，那么不用扩展，因为父节点已经扩展过
102
if
(is_linable(t.m_d, i))
103
continue
;
104
105
//
下一个位置的行，列坐标，方向，转次
106
int
nx
=
t.m_x
+
g_dir[i][
0
];
107
int
ny
=
t.m_y
+
g_dir[i][
1
];
108
int
nd
=
i;
109
int
nc
=
t.m_c
+
1
;
110
111
//
如果下一个位置可达
112
while
(is_reachable(nx, ny)) {
113
//
如果已经找到一条路径
114
if
(is_arrived(nx, ny))
115
return
true
;
116
117
//
如果此点还有继续扩展能力
118
if
(nc
<
2
)
//
因为下一次扩展肯定要转向，所以转次至少还剩1
119
q.push(Status(nx, ny, nc, nd));
120
121
nx
+=
g_dir[i][
0
];
122
ny
+=
g_dir[i][
1
];
123
}
//
while
124
}
//
for
125
}
//
while
126
127
return
false
;
128
}
129
130
int
main() {
131
while
(EOF
!=
scanf(
"
%d %d
"
,
&
g_N,
&
g_M)) {
132
if
(g_N
==
0
&&
g_M
==
0
)
133
break
;
134
135
//
输入
136
for
(
int
i
=
1
; i
<=
g_N; i
++
)
137
for
(
int
j
=
1
; j
<=
g_M; j
++
)
138
scanf(
"
%d
"
, g_maze[i]
+
j);
139
140
scanf(
"
%d
"
,
&
g_T);
141
g_ans
=
0
;
142
for
(
int
i
=
0
; i
<
g_T; i
++
) {
143
scanf(
"
%d %d %d %d
"
,
&
g_x1,
&
g_y1,
&
g_x2,
&
g_y2);
144
145
//
搜索前预判断
146
//
如果有一点为空
147
if
(g_maze[g_x1][g_y1]
==
0
||
g_maze[g_x2][g_y2]
==
0
)
148
continue
;
149
//
如果两点在同一点
150
if
(g_x1
==
g_x2
&&
g_y1
==
g_y2)
151
continue
;
152
//
如果两点不一样
153
if
(g_maze[g_x1][g_y1]
!=
g_maze[g_x2][g_y2])
154
continue
;
155
156
//
预处理
157
int
t
=
g_maze[g_x1][g_y1];
158
g_maze[g_x1][g_y1]
=
0
;
159
g_maze[g_x2][g_y2]
=
0
;
160
161
//
如果能联通，
162
if
(special_bfs())
163
g_ans
+=
2
;
164
else
{
//
如果不能连同，则复原预处理
165
g_maze[g_x1][g_y1]
=
t;
166
g_maze[g_x2][g_y2]
=
t;
167
}
168
}
169
170
printf(
"
%d\n
"
, g_ans);
171
}
172
return
0
;
173
}
174
175
/*
176
测试数据：
177
3 4
178
1 1 2 2
179
3 3 4 4
180
2 2 1 1
181
6
182
1 1 1 2
183
1 3 1 4
184
2 1 2 2
185
2 3 2 4
186
3 1 3 2
187
3 3 3 4
188
189
3 4
190
1 2 1 2
191
3 4 3 4
192
2 1 2 1
193
7
194
1 1 1 1
195
1 1 1 2
196
1 3 1 4
197
2 1 2 2
198
2 3 2 4
199
3 1 3 2
200
3 3 3 4
201
202
3 4
203
1 2 1 2
204
1 1 2 2
205
2 2 1 1
206
3
207
2 3 2 4
208
2 2 3 3
209
3 2 1 4
210
211
2 3
212
0 0 0
213
0 0 0
214
2
215
1 1 1 1
216
1 1 1 2
217
218
0 0
219
220
*/
转载于:https://www.cnblogs.com/nysanier/archive/2011/03/27/1996831.html
