countluck.go

package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

// Complete the countLuck function below.
type coord struct {
	x, y, ways int
}

var dirs = [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

func countLuck(matrix []string, k int32) string {
	var m, n = len(matrix), len(matrix[0])
	var start, finish coord
	var visited, path []coord
	var waves int32

	if len(matrix) == 0 {
		if k == 0 {
			return "Impressed"
		}
		return "Oops!"
	}

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if string(matrix[i][j]) == "M" {
				start = coord{i, j, 0}
			}
			if string(matrix[i][j]) == "*" {
				finish = coord{i, j, 0}
			}
		}
	}

	dfs(matrix, &visited, &path, start, finish)
	for _, c := range path {
		if c.x == start.x && c.y == start.y && c.ways > 1 {
			waves++
		} else if c.ways > 2 {
			waves++
		}
	}
	if waves == k {
		return "Impressed"
	}
	return "Oops!"
}

func dfs(matrix []string, visited, path *[]coord, start, finish coord) bool {
	var m, n = len(matrix), len(matrix[0])

	if start == finish {
		return true
	}

	for _, dir := range dirs {
		x, y := start.x+dir[0], start.y+dir[1]
		if x < 0 || x >= m || y < 0 || y >= n || string(matrix[x][y]) == "X" {
			continue
		}
		next := coord{x, y, 0}
		if contains(*visited, next) {
			continue
		}
		*visited = append(*visited, start)
		start.ways = ways(matrix, start)
		found := dfs(matrix, visited, path, next, finish)
		if found {
			*path = append(*path, start)
			return true
		}
	}
	return false
}

func contains(slice []coord, item coord) bool {
	for _, v := range slice {
		if v.x == item.x && v.y == item.y {
			return true
		}
	}
	return false
}

func ways(matrix []string, cell coord) int {
	var ways int
	var m, n = len(matrix), len(matrix[0])
	for _, dir := range dirs {
		x, y := cell.x+dir[0], cell.y+dir[1]
		if x < 0 || x >= m || y < 0 || y >= n || string(matrix[x][y]) == "X" {
			continue
		}
		ways++
	}
	return ways
}

func main() {
	reader := bufio.NewReaderSize(os.Stdin, 1024*1024)

	stdout, err := os.Create(os.Getenv("OUTPUT_PATH"))
	checkError(err)

	defer stdout.Close()

	writer := bufio.NewWriterSize(stdout, 1024*1024)

	tTemp, err := strconv.ParseInt(readLine(reader), 10, 64)
	checkError(err)
	t := int32(tTemp)

	for tItr := 0; tItr < int(t); tItr++ {
		nm := strings.Split(readLine(reader), " ")

		nTemp, err := strconv.ParseInt(nm[0], 10, 64)
		checkError(err)
		n := int32(nTemp)

		var matrix []string

		for i := 0; i < int(n); i++ {
			matrixItem := readLine(reader)
			matrix = append(matrix, matrixItem)
		}

		kTemp, err := strconv.ParseInt(readLine(reader), 10, 64)
		checkError(err)
		k := int32(kTemp)

		result := countLuck(matrix, k)

		fmt.Fprintf(writer, "%s\n", result)
	}

	writer.Flush()
}

func readLine(reader *bufio.Reader) string {
	str, _, err := reader.ReadLine()
	if err == io.EOF {
		return ""
	}

	return strings.TrimRight(string(str), "\r\n")
}

func checkError(err error) {
	if err != nil {
		panic(err)
	}
}