I've got the following assignment for one of my classes. My current solution is showed below the assignment text. I am finding the correct result but my code is too slow to give me the necessary points needed.

The Assignment

Josefine and her little sister is playing a game called Letter Labyrinth. In this game, a N times N matrix is filled with As and Bs (see example below). The challenge is to find the shortest path that leads from the top left corner to the lower right corner. The path must alternate between A's and B's, ie. when reading the letters on the path it should spell out ABABABA... The path can only go up/right/down/left. In the following example the shortest path has been marked with lower case letters.

aAaba
bBbBb
abaAa
ABBBb
AAAAa

As they find it difficult to determine if they have found the shortest path, they need you to write a program to verify this for them.

Input format

Line 1: The integer N
Line 2..N+1: The N times N matrix of letters (A or B) corresponding to the labyrinth.

Output format

Line 1: The number of letters on the shortest path from the top left corner to the lower right corner.

My code

First i've made a Graph class. Here i will primarily use the shortPath function of the class.

class Graph:
 # Laver en graph, hvis intet input så laves en tom graph.
 # Input et dict med hver verticy samt dens edges. 
 def __init__(self, gd=None):
 if gd is None:
 gd = 
 self.gd = gd

 def genEdges(self):
 edges = []
 # Her er v vertecies og n er neighbours til hver edge. 
 for v in self.gd:
 for n in self.gd[v]:
 if n,v not in edges:
 edges.append(v,n)
 return edges

 def addVert(self,v):
 # Tilføjer vertex med tom liste af edges.
 if v not in self.gd:
 self.gd[v] = []

 def addEdge(self, edges):
 # Her skal edges være en liste med 2 verticies som skal forbindes.
 self.gd[edges[0]].append(edges[1])
 self.gd[edges[1]].append(edges[0])

 def pVert(self):
 return list(self.gd.keys())

 def pEdges(self):
 return self.genEdges()

 def BFS(self, v):
 # Laver dict til at tjekke om en verticy er besøgt
 b = 
 for i in self.gd:
 b[i] == False

 b[v] = True

 # Laver en que
 q = []
 q.append[v]

 paths = 

 while q:
 v = q.pop(0)
 print(v)

 for i in self.gd[v]:
 if b[i] == False:
 q.append(i)
 b[i] = True

 def shortPath(self, start, slut, path = list()):
 # Laver en list som vejen til slut.
 path = path + [start]
 # Tjekker om start og slut er den samme
 if start == slut:
 return path

 # Tjekker om start er i grafen
 if start not in self.gd:
 return None

 # Laver en variabel til at gemme shortest path
 sPath = []
 for v in self.gd[start]:
 if v not in path:
 nPath = self.shortPath(v, slut, path)
 if len(nPath) > 0:
 if len(sPath) == 0 or len(nPath) < len(sPath):
 sPath = nPath
 return sPath

Afterwards ill create and use the graph class in the following code.

g = Graph()

N = int(input())

countA = 1
countB = 1

for i in range(0,N):
 Line = list(input())

 for j in range(0,len(Line)):
 if Line[j] == "A":
 Line[j] = "A" + str(countA)
 countA += 1
 elif Line[j] == "B":
 Line[j] = "B" + str(countB)
 countB += 1

 # Tilføjer Vertecies
 g.addVert(Line[j])

 if Line[j][0] == "A":
 if j > 0 and Line[j-1][0] == "B":
 # Tilføjer Edges til venstre
 g.addEdge([Line[j],Line[j-1]])
 if Line[j][0] == "A":
 if i > 0 and Line2[j][0] == "B":
 g.addEdge([Line[j],Line2[j]])

 if Line[j][0] == "B":
 if j > 0 and Line[j-1][0] == "A":
 # Tilføjer Edges til venstre
 g.addEdge([Line[j],Line[j-1]])
 if i > 0 and Line2[j][0] == "A":
 g.addEdge([Line[j],Line2[j]])
 # Tilføjer edges opad

 if i == 0:
 Start = Line[0]

 if i == N-1:
 End = Line[-1]

 Line2 = Line


sp = g.shortPath(Start,End)
print(len(sp))

My problem is as described above that the code is too slow. If anyone knows a way to optimize it i would really appreciate it.

Thanks in advance.

Your code looks way more complicated to me, solving this problem with DFS is good aapproach, but I think you have unnecessary loops in your implementation.
Pseudo code:

import Queue
# storeing edges
Class Edge(i,j):
 isVisited
 distance = -1
 i
 j
 char
# main function to call
DFS(input):
 maxIndex = getN()
 q = Queue.Queue()
 edgeMatrix = initNtimesNMartixWithNulls()
 end = False
 q.put(edgeMartix[0][0];
 for i in range(0,N):
 for(j in range(0,N):
 char = someFunc(input,i,j)
 edgeMartix[i][j] = Edge(i,j)
 while not q.empty() and not end:
 e = q.get()
 end = addElement(q, e.i +1, e.j, q.char, q.distance) or end
 end = addElement(q, e.i -1, e.j, q.char, q.distance) or end
 end = addElement(q, e.i, e.j +1, q.char,q.distance) or end
 end = addElement(q, e.i, e.i -1, q.char, q.distance) or end
 return edgeMartix[N-1][N-1]

addElement(edgeMartix, q,i,j,maxIndex, char, dist):
 if(i < 0 or i > maxIndex or j < 0 or i > maxIndex):
 return False
 e = edgeMartix[i][j]
 if (not e.isVisited and e.char != char):
 e.isVisited = True
 e.distance = distance + 1
 q.put(e)
 if (i == max and j == max ) :
 return True
 return False