连连看之Golang版本

连连看是一种很受大家欢迎的小游戏。下面四张图给出了最基本的消除规则：

图 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
}