Введение в Python

Решите задачу 

Аналогичный код на Java:

import java.util.*;

class solution {
  static Stack stack = new Stack();
  static Stack tree = new Stack();
  static Stack path = new Stack();
	
  static boolean[][] visited;	
  static pair[][] prev;
  static int[] dr = {-1,0,0,1}; 
  static int[] dc = {0,-1,1,0};
  static String ds = "^<>v";
	
  static void dfs_iterative(int r, int c, int pacman_r, int pacman_c, int food_r, int food_c, String [] grid) {
     pair pacman_pair = new pair(pacman_r, pacman_c);
     stack.push(pacman_pair);
     visited[pacman_r][pacman_c] = true;
     boolean solved = false;
     while (!stack.isEmpty()&&!solved) {  	
        pacman_pair = stack.pop();				
	pacman_r = pacman_pair.first; pacman_c = pacman_pair.second;
	solved = pacman_r == food_r && pacman_c == food_c;
			
        for (int direction = 0; direction < 4; direction++) {
	   int new_pacman_r = pacman_r + dr[direction];
	   int new_pacman_c = pacman_c + dc[direction];
	   if (0 <= new_pacman_r && new_pacman_r < r && 0 <= new_pacman_c && new_pacman_c < c)
	   {
	       char ch = grid[new_pacman_r].charAt(new_pacman_c);	    			
	       if (ch != '%' && ch != 'P' && !visited[new_pacman_r][new_pacman_c]) {
    		   pair new_pacman_pair = new pair(new_pacman_r, new_pacman_c);    					
    		   stack.push(new_pacman_pair);
    		   visited[new_pacman_r][new_pacman_c] = true;				
		   setCharAt(ds.charAt(direction), new_pacman_r, new_pacman_c, grid);
		   prev[new_pacman_r][new_pacman_c] = pacman_pair;
	        }
	    }
	}
    	tree.push(pacman_pair);
   }		
}
	
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int pacman_r = sc.nextInt();
    int pacman_c = sc.nextInt();

    int food_r = sc.nextInt();
    int food_c = sc.nextInt();

    int r = sc.nextInt();
    int c = sc.nextInt();
    
    String grid[] = new String[r];

    for(int i = 0; i < r; i++) {
        grid[i] = sc.next();
    }       
    visited = new boolean[r][c];        
    prev = new pair[r][c]; 
    dfs_iterative( r, c, pacman_r, pacman_c, food_r, food_c, grid);        
    System.out.println(tree.size());
    reverse_stack(tree);
    print_stack(tree);
    convert_prev_to_stack(prev, new pair(food_r, food_c));
    System.out.println(path.size()-1);
    print_stack(path);
    sc.close();
}
	
	static void reverse_stack(Stack stack)
	{
		ArrayDeque deque = new ArrayDeque();
    	while (!stack.isEmpty())
    		deque.addFirst(stack.pop());    	
    	while (!deque.isEmpty()) {
    		stack.push(deque.getLast());
    		deque.removeLast();
    	}
	}
	
	static void convert_prev_to_stack(pair[][] prev, pair food_pos){
		path = new Stack();
		pair pacman_pos = food_pos ;
		while (pacman_pos != null)
		{
			path.push(pacman_pos);
			pacman_pos = prev[pacman_pos.first][pacman_pos.second];
		}
	}
	
	static void print_stack(Stack path)
	{
    	while (!path.isEmpty()) {   		
			pair p = path.pop();
			System.out.println("" + p.first + " " + p.second);
    	}
	}
	
	
	static void setCharAt(char ch, int pacman_r, int pacman_c, String[] grid){
		StringBuilder sb = new StringBuilder(grid[pacman_r]);
		sb.setCharAt(pacman_c, ch);
		grid[pacman_r] = sb.toString();		
	}
}

class pair{
	public int first;
	public int second;
	public pair(int f, int s) { first = f; second = s; }
	@Override
	public String toString() {
		return "" + first + " " + second;
	}
}