994.py

'''
In a given grid, each cell can have one of three values:

the value 0 representing an empty cell;
the value 1 representing a fresh orange;
the value 2 representing a rotten orange.
Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange.  If this is impossible, return -1 instead.
'''

class Solution(object):
    def valid(self, row, col, row_size, col_size):
        return row >= 0 and col >= 0 and row < row_size and col < col_size
    
    def orangesRotting(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        queue = []
        for row_index in range(len(grid)):
        	for col_index in range(len(grid[0])):
        		if grid[row_index][col_index] == 2:
        			queue.append((row_index, col_index))

        result = 0
        queue.append((-1, -1))
        while queue:
        	flag = False
        	print queue
        	while(queue[0][0] != -1 and queue[0][1] != -1):
        		(row, col) = queue[0]
        		if self.valid(row+1, col, len(grid), len(grid[0])) and grid[row+1][col] == 1 :
        			if not flag:
        				result += 1
        				flag =True
        			grid[row+1][col] = 2
        			row += 1
        			queue.append((row, col))
        			row -= 1
        		if self.valid(row-1, col, len(grid), len(grid[0])) and grid[row-1][col] == 1 :
        			if not flag:
        				result += 1
        				flag =True
        			grid[row-1][col] = 2
        			row -= 1
        			queue.append((row, col))
        			row += 1
        		if self.valid(row, col+1, len(grid), len(grid[0])) and grid[row][col+1] == 1 :
        			if not flag:
        				result += 1
        				flag =True
        			grid[row][col+1] = 2
        			col += 1
        			queue.append((row, col))
        			col -= 1
        		if self.valid(row, col-1, len(grid), len(grid[0])) and grid[row][col-1] == 1 :
        			if not flag:
        				result += 1
        				flag =True
        			grid[row][col-1] = 2
        			col -= 1
        			queue.append((row, col))
        			col += 1
        		queue.pop(0)
        	queue.pop(0)
        	if queue:
        		queue.append((-1, -1))
        for row_index in range(len(grid)):
        	for col_index in range(len(grid[0])):
        		if grid[row_index][col_index] == 1:
        			return -1
        return result