At first glance, you code appears to have a lot of complicated and repetitive sections. That's a bad smell, and often a hint that you should either split the repetitive parts off into a function or otherwise reorganize your code to get rid of the repetition. (Sometimes, one option can be to just simplify the code until the repetitive parts become trivial.)
A lot of the complexity in the repetitive parts of your code seems to come from your decision to store the grid as a dictionary of dictionaries. There's a couple of ways to simplify that:
In Python, dictionary keys can be tuples. So you can just do:
visited = {}
# ...
if (row, col) not in visited:
# do something
visited[row, col] = True
else:
# do something else
(Also, you shouldn't name your dictionary dict, both because it's the name of the dictionary type in Python and also because it's an uninformative name that doesn't explain what you're using the dictionary for. Call its something meaningful like visited_cells or just visited instead.)
Also, since you're really only using the dictionary as a set, why not make it one? The code can look exactly the same as above, except that you'll start with visited = set() instead of visited = {}, and mark cells as visited with visited.add((row, col)).
Alternatively, instead of using a dictionary or a set, you could just use a two-dimensional array (implemented e.g. as a list of lists) of booleans, initialized to all False, something like this:
visited = [[False] * cols for row in range(rows)]
# ...
if not visited[row][col]:
# do something
visited[row][col] = True
else:
# do something else
I suspect this is what the exercise is actually expecting you to do. However, I do rather like your idea of using a dictionary (or a set) instead, and I'm only mentioning this alternative for the sake of completeness.
One advantage of using a dictionary or a set to store the visited cells is that it means you don't actually need to care about the boundaries of the grid, since the dictionary can accommodate arbitrary large or small coordinates. In particular, you don't actually need to adjust the input coordinates from one-based to zero-based indexing (and back again for output), so you can just eliminate those parts of your code.
Another way to reduce the repetitiveness of your code is to observe that all the sections for handling movement in different directions look basically the same, except for the index (row or column) being changed and the step size (+1 or -1) it's being changed by. If you defined a dictionary that mapped the N/S/E/W direction letters to the corresponding coordinate offsets, something like this:
directions = {
'N': (-1, 0),
'S': (+1, 0),
'W': (0, -1),
'E': (0, +1),
}
then you could combine all those sections into a single one, something like this:
row = start_row
col = start_col
visited = {(row, col)} # loop below assumes current square is always marked as visited
for compass_heading in instructions:
row_step, col_step = directions[compass_heading]
while (row, col) in visited:
row += row_step
col += col_step
visited.add((row, col))
(Note that I renamed a few of your variables here. You should not use variables named startRow and startCol to store the current row and column, since that's just plain misleading, and in any case variable names in Python should be written in snake_case instead of camelCase. And a is just an awful variable name, so I renamed it to instructions. You already have a variable named that, but it's completely unnecessary and unused. You could just use the dummy variable _ in the list assignment instead.)
As for making the code faster, I see no obvious trivial opportunities there. Using a single set instead of a dictionary of dictionaries is probably somewhat faster, perhaps even twice as fast if your running time is dominated by dictionary lookups, but not orders of magnitude faster. A list of lists of booleans might be even faster for small grids, but the time to initialize it scales with the size of the grid, whereas the time to set up a single-element set (or dictionary) is basically constant. Anyway, I'd suggest first focusing on cleaning up your code, and only worrying about optimization if it's still too slow after that.
If it is, a good starting point is to focus on worst-case performance, i.e. to think about how a sneaky test case designed might make your code run as slowly as possible, and try to find ways to counter that.
In particular, the worst case input for your algorithm (with or without the improvements I suggested above) is something like NSNSNSNSNSNSNSNSNSNSNSNSNS..., which forces the robot to move back and forth over an increasingly long stretch of visited cells, leading to an O(n²) execution time.
One way to avoid that would be to store a dictionary of "signposts" recording, for each move we make, where we ended up on the grid after that move. That way, the next time the robot finds itself in the same square and moving in the same direction, it can skip all the cells in between. Also, since the movement rules are symmetric, we can also leave behind "backwards" signposts recording where the robot came from as it entered each cell, allowing us to skip the intervening cells in the opposite direction as well.
A quick sketch of how to implement that might look something like this:
# look-up table of (row_step, col_step, opposite_heading) for each compass heading
directions = {
'N': (-1, 0, 'S'),
'S': (+1, 0, 'N'),
'W': (0, -1, 'E'),
'E': (0, +1, 'W'),
}
row = start_row
col = start_col
visited = {(row, col)} # loop below assumes current square is always marked as visited
signposts = {}
for compass_heading in instructions:
last_row = row
last_col = col
row_step, col_step, opposite_heading = directions[compass_heading]
while (row, col) in visited:
if (row, col, compass_heading) in signposts:
# we've been this way before!
row, col = signposts[row, col, compass_heading]
row += row_step
col += col_step
visited.add((row, col))
signposts[last_row, last_col, compass_heading] = (row, col)
signposts[row, col, opposite_heading] = (last_row, last_col)
Note that, as written, the signposts dictionary always grows linearly with the size of the input. You may obtain some additional speed and memory savings by removing old signposts as they become unnecessary.
In particular, we can safely remove any signposts we encounter as soon as we've used them, since they will either become useless or get overwritten anyway. We can also safely remove any backwards signposts that we pass, since those also become useless. With those changes, the optimized inner loop would look something like this:
while (row, col) in visited:
if (row, col, compass_heading) in signposts:
# follow and remove signposts; any that are still valid will be restored below
row, col = signposts.pop((row, col, compass_heading))
del signposts[row, col, opposite_heading]
row += row_step
col += col_step
However, note that the set of visited cells will still grow linearly, and that meandering paths like, say, NESWNESWNESWNESWNESW... can still leave behind a linearly growing number of signposts, so the worst-case memory consumption is still linear even with this optimization.
Ps. Here's a simple online demo of the signpost-optimized algorithm I describe above, with some debug print statements added. Feel free to play around with it to see how it works.
