Autonomous Car With Two Turns

Problem Statement

Autonomous Car With Two Turns You are writing the navigation program for an autonomous car that is still in development, and the prototype has a serious drawback: on its way from the starting point to the finish point the car can make no more than two turns . The testing center is a grid of b rows and p columns. Some cells contain road blockages and cannot be entered. Find a way from the starting point to the finish point that has no more than two turns and does not contain cells with blockages, or determine that it is impossible to drive to the end. The car can only move upwards, downwards, to the left, and to the right. Input Format The first line of input contains an integer b . The second line of input contains an integer p . The next lines of input contain b lines with p space-separated characters. These characters are allowed to appear: o — an empty cell x — a cell with road blockages Q — the starting point W — the ending point Q and W will appear only once. Output Format Print D