Feb-05-2018, 11:44 AM
Ok, so here´s the drill: I´m doing a problem that receives a matrix of size NxN (the problem called it a "mine", hence the variable name used) containing 0´s and 1´s, and then finds the path that goes throw the least number of 1´s and then prints out the number of 1´s that the path had to go throw. So this code i made works by receiving the input variable N, and then a matrix of size NxN containing 0´s and 1´s. After that, i generate a tuple that contains all the possible paths (the letters "R" and "D" represent the way the path is going, either right or down, these are the only moves allowed in the problem´s statement). After that, i go through each possible path, and then i have a variable that counts how many 1´s did it have to go throw. The variable "min" then receives the value of the counter for each path if that counter is smaller than the previous minimum path counter. In this way, when i print the variable "min", i should get the minimum number of 1´s you have to go throw in order to complete the path of the matrix (go from [0][0] to [N-1][N-1]), but in the simples test case of a 2x2 matrix [[0, 0], [1, 0]] which is supposed to be 0, obviously, i´m getting 1. Can someone help figure this out please? (The code is down below)
from itertools import permutations
N = int(input())
Mine = [input().split() for x in range(N)]
Mine = [[int(i) for i in x] for x in Mine]
sample_path = "D"*(N-1)+"R"*(N-1)
paths = set(permutations(sample_path, 2*(N-1)))
Min = N**2
for i in list(paths):
counter = 0
pos = [0, 0]
for j in i:
if j == 'D':
if Mine[pos[0]+1][pos[1]] == 1:
counter += 1
pos[0] += 1
elif j == 'R':
if Mine[pos[0]][pos[1]+1] == 1:
counter += 1
pos[1] += 1
if counter < Min: Min = counter
print(Min)
