笔试题一道

package main

import "fmt"

//给定一个8x8的棋盘（二维数组）,放入若干个车（1），检查这些车是否相互攻击，若互相攻击，输出true //0 1 0 0 0 0 0 0 //0 0 0 0 0 0 0 0 //0 0 0 1 0 0 0 0 //0 0 0 0 0 0 0 0 //0 0 0 0 0 0 0 0 //0 0 0 0 0 0 0 0 //0 0 0 0 0 0 0 0 //0 0 0 0 0 0 0 0 //面试官 //若初始不互相攻击，那么还能放几个不互相攻击的车， 分别放在哪里？输出所有方案。

func main() { hitInfo := [][]int{ {0, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0}, } a, b := checkCarHit(hitInfo) fmt.Printf("%+v,%+v\n", a, b) }

func checkCarHit(carInfo [][]int) (int, bool) { if len(carInfo) <= 0 { return 0, false } row := len(carInfo) col := len(carInfo[0]) carRowArray := make([]bool, 8) //记录第几行有车了 carColArray := make([]bool, 8) for i := 0; i < row; i++ { for j := 0; j < col; j++ { if carInfo[i][j] == 1 { if carRowArray[i] { return 0, true } carRowArray[i] = true if carColArray[j] { return 0, true } carColArray[j] = true } } } canPutCount := 0 for _, i := range carRowArray { if !i { canPutCount++ } } printPutArray(carRowArray, carColArray, 0, carInfo)

return canPutCount, false

}

//一列列去生成？nowRow记录生成到第几行，生成到最后一步回退,carInfo生成的结果 func printPutArray(carRowArray, carColArray []bool, nowCol int, carInfo [][]int) {

if nowCol >= 7 {
    if carColArray[nowCol] {
        PrintCar(carInfo)
        return
    }
    for i := 0; i < 8; i++ {
        if !carRowArray[i] {
            carInfo[i][nowCol] = 1
            PrintCar(carInfo)
            carInfo[i][nowCol] = 0
            return
        }
    }
}
for i := nowCol; i < 7; i++ {
    if carColArray[i] {
        continue
    }
    for j := 0; j < 8; j++ {
        if !carRowArray[j] {
            carRowArray[j] = true
            carInfo[j][i] = 1
            k := i+1
            printPutArray(carRowArray, carColArray, k, carInfo)
            carRowArray[j] = false
            carInfo[j][i] = 0
        }
    }
}

}

func PrintCar(carInfo [][]int) { fmt.Println("----------") for _, car := range carInfo { fmt.Printf("%+v\n", car) } }