Super Knight

import sys
from collections import deque
import time

M = int(sys.argv[1])
N = int(sys.argv[2])
p = int(sys.argv[3])
q = int(sys.argv[4])
X = int(sys.argv[5])
Y = int(sys.argv[6])
U = int(sys.argv[7])
V = int(sys.argv[8])
move = zip([-p,p,-p,p,-q,-q,q,q],[-q,-q,q,q,-p,p,-p,p])

if 2 > M or N > 100:
    print("Constraint broken\n")
    print("2 <= M and N <= 100\n")
    exit(0)

if 1 > X or X > M or 1 > Y or Y > N:
    print ("Constraint broken\n")
    print ("1 <= X <= M, 1 <= Y <= N\n")
    exit(0)

if 1 > U or U > M or 1 > V or V > N:
    print ("Constraint broken\n")
    print ("1 <= U <= M, 1 <= V <= N\n")
    exit(0)

# Move to a 0 based coordinate system
X = X - 1
Y = Y - 1
U = U - 1
V = V - 1

board = [[[] for x in range(N)] for y in range(M)]

def printBoard():
    print "   ",
    for i in range(N):
        print i,
    print ""
    print "_"*((N*2)+4)
    for i in range(M):
        print i, "|",
        for j in range(N):
            print len(board[i][j]),
        print "\n"
    print "\n"

def insideBoard(x, y):
    return x >= 0 and x < M and y >= 0 and y < N

def depthFirstSearch(fromX, fromY, targetX, targetY, path):
    board[fromX][fromY] = path

    if fromX == targetX and fromY == targetY:
        return
    for (x,y) in move:
        x = fromX+x
        y = fromY+y
        if insideBoard(x, y) and (len(board[x][y]) == 0 or (len(path) + 1) < len(board[x][y])):
            newPath = path[:]
            newPath.append((x, y))
            depthFirstSearch(x, y, targetX, targetY, newPath)

def breadthFirstSearch(fromX, fromY, targetX, targetY, path):
    toSearch = []

    for (x, y) in move:
        x = fromX+x
        y = fromY+y
        if insideBoard(x, y) and (len(board[x][y]) == 0 or (len(path)+1) < len(board[x][y])):
            newPath = path[:]
            newPath.append((x, y))
            toSearch.append(((x, y), newPath))


    while True:
        ((fromX, fromY), path) = toSearch.pop(0)
        board[fromX][fromY] = path

        if fromX == targetX and fromY == targetY:
            break

        for (x, y) in move:
            x = fromX+x
            y = fromY+y
            if insideBoard(x, y) and (len(board[x][y]) == 0 or (len(path)+1) < len(board[x][y])):
                newPath = path[:]
                newPath.append((x, y))
                toSearch.append(((x, y), newPath))

        if len(toSearch) == 0:
            break

board = [[[] for x in range(N)] for y in range(M)]
t0 = time.time()
breadthFirstSearch(X, Y, U, V, [(X, Y)])
t1 = time.time()
printBoard()
print board[U][V]
print "Time:", t1-t0

board = [[[] for x in range(N)] for y in range(M)]
t0 = time.time()
depthFirstSearch(X, Y, U, V, [(X, Y)])
t1 = time.time()
printBoard()
print board[U][V]
print "Time:", t1-t0