连连看是一种很受大家欢迎的小游戏。下面四张图给出了最基本的消除规则：
图 A 中出现在同一直线上无障碍的圈圈可以消除；图 B 中两个圈圈可以通过一次转弯消除；图 C 和图 D 中，两个圈圈可以通过两次转弯消除。
首先需要判断路上是否有障碍物
func isBlocked(full [][]byte,i,j int)bool {
if full[i][j]=='.'{
return false
}
return true
}
判断是否是图A的情况，则需要判断水平或者竖直是否能直接联通
/检测水平之间是否联通
func horizon(full [][]byte,x1,y1,x2,y2 int)bool {
if x1==x2&&y1==y2{
return false
}
if x1!=x2{
return false
}
start := min(y1,y2)
end := max(y1,y2)
for j:=start+1;j<end;j++{
if isBlocked(full,x1,j){
return false
}
}
return true
}
//竖直是否联通
func vertical(full [][]byte,x1,y1,x2,y2 int)bool{
if x1==x2&&y1==y2{
return false
}
if y1!=y2{
return false
}
start := min(x1,x2)
end := max(x1,x2)
for j:=start+1;j<end;j++{
if isBlocked(full,j,y1){
return false
}
}
return true
}
判断图B的情况，即如下图所示
能A-C竖直+C-B水平
或者A-D水平，D-B竖直
//C B(x2,y2)
//A(x1,y1) D
//单个拐角之间是否能联通
func sigTurn(full [][]byte,x1,y1,x2,y2 int)bool {
if x1==x2&&y1==y2{
return false
}
c_x,c_y := x2,y1
d_x,d_y := x1,y2
var ret bool
if !isBlocked(full,c_x,c_y){
ret = ret||(horizon(full,x1, y1, c_x, c_y) && vertical(full,c_x, c_y, x2, y2))
}
if !isBlocked(full,d_x,d_y){
ret = ret||(horizon(full,x1, y1, d_x, d_y) && vertical(full,d_x, d_y, x2, y2))
}
return ret
}
判断图C和图D的情况
两个拐角检测 = 一个拐角检测 && (水平检测 || 垂直检测)
如图，水平、垂直分别穿过 A B 共有四条直线，扫描直线上所有不包含 A B 的点，看是否存在一点 C ，满足以下任意一项：
A 点至 C 点通过水平或垂直检测，C 点至 B 点可通过一个拐角连接。（图中用 C 表示）
A 点至 C 点可通过一个拐角连接，C 点至 B 点通过水平或垂直连接。（图中用 C 下划线表示）
//两个拐角是否能联通
//两个拐角意思就是一个水品或者垂直到一个中间点，又能拐角到另一个点
func twoTurn(full [][]byte,x1,y1,x2,y2 int)bool {
if x1==x2&&y1==y2{
return false
}
l1 := len(full)
l2 := len(full[0])
for i:=0;i<l1;i++{
for j:=0;j<l2;j++{
if i!=x1&&i!=x2&&j!=y1&&j!=y2{//不在两点的水平或者垂直线上
continue
}
if (i==x1&&j==y1)||(i==x2&&j==y2){
continue
}
if isBlocked(full,i,j){
continue
}
if sigTurn(full,x1,y1,i,j)&&(horizon(full,x1,y1,i,j)||vertical(full,x1,y1,i,j)){
return true
}
if sigTurn(full,i,j,x2,y2)&&(horizon(full,i,j,x2,y2)||vertical(full,i,j,x2,y2)){
return true
}
}
}
return false
}
附上完整代码
package main
import (
"bufio"
"fmt"
"os"
)
func main() {
var m,n int
fmt.Scanf("%d %d",&m,&n)
var qipan = make([][]byte,0)
bfio := bufio.NewReader(os.Stdin)
for i:=0;i<m;i++{
tmp,_:=bfio.ReadBytes('\n')
qipan = append(qipan,tmp)
}
fmt.Println(qipan)
var op int
fmt.Scanf("%d",&op)
for i:=0;i<op;i++{
var x1,y1,x2,y2 int
fmt.Scanf("%d %d %d %d",&x1,&y1,&x2,&y2)
if qipan[x1-1][y1-1]==qipan[x2-1][y2-1]&&remove(qipan,x1-1,y1-1,x2-1,y2-1){
fmt.Println("YES")
}else {
fmt.Println("NO")
}
}
}
func remove(full [][]byte,x1,y1,x2,y2 int)bool{
var ret bool
ret = horizon(full,x1,y1,x2,y2)
if ret{
full[x1][y1],full[x2][y2] = '.','.'
return true
}
ret = vertical(full,x1,y1,x2,y2)
if ret{
full[x1][y1],full[x2][y2] = '.','.'
return true
}
ret = sigTurn(full,x1,y1,x2,y2)
if ret{
full[x1][y1],full[x2][y2] = '.','.'
return true
}
ret = twoTurn(full,x1,y1,x2,y2)
if ret{
full[x1][y1],full[x2][y2] = '.','.'
return true
}
return false
}
func isBlocked(full [][]byte,i,j int)bool {
if full[i][j]=='.'{
return false
}
return true
}
//检测水平之间是否联通
func horizon(full [][]byte,x1,y1,x2,y2 int)bool {
if x1==x2&&y1==y2{
return false
}
if x1!=x2{
return false
}
start := min(y1,y2)
end := max(y1,y2)
for j:=start+1;j<end;j++{
if isBlocked(full,x1,j){
return false
}
}
return true
}
//竖直是否联通
func vertical(full [][]byte,x1,y1,x2,y2 int)bool{
if x1==x2&&y1==y2{
return false
}
if y1!=y2{
return false
}
start := min(x1,x2)
end := max(x1,x2)
for j:=start+1;j<end;j++{
if isBlocked(full,j,y1){
return false
}
}
return true
}
//C B(x2,y2)
//A(x1,y1) D
//单个拐角之间是否能联通
func sigTurn(full [][]byte,x1,y1,x2,y2 int)bool {
if x1==x2&&y1==y2{
return false
}
c_x,c_y := x2,y1
d_x,d_y := x1,y2
var ret bool
if !isBlocked(full,c_x,c_y){
ret = ret||(horizon(full,x1, y1, c_x, c_y) && vertical(full,c_x, c_y, x2, y2))
}
if !isBlocked(full,d_x,d_y){
ret = ret||(horizon(full,x1, y1, d_x, d_y) && vertical(full,d_x, d_y, x2, y2))
}
return ret
}
//两个拐角是否能联通
//两个拐角意思就是一个水品或者垂直到一个中间点，又能拐角到另一个点
func twoTurn(full [][]byte,x1,y1,x2,y2 int)bool {
if x1==x2&&y1==y2{
return false
}
l1 := len(full)
l2 := len(full[0])
for i:=0;i<l1;i++{
for j:=0;j<l2;j++{
if i!=x1&&i!=x2&&j!=y1&&j!=y2{//不在两点的水平或者垂直线上
continue
}
if (i==x1&&j==y1)||(i==x2&&j==y2){
continue
}
if isBlocked(full,i,j){
continue
}
if sigTurn(full,x1,y1,i,j)&&(horizon(full,x1,y1,i,j)||vertical(full,x1,y1,i,j)){
return true
}
if sigTurn(full,i,j,x2,y2)&&(horizon(full,i,j,x2,y2)||vertical(full,i,j,x2,y2)){
return true
}
}
}
return false
}
func max(i,j int)int {
if i > j{
return i
}
return j
}
func min(i,j int)int {
if i < j{
return i
}
return j
}
