Skip to content

Latest commit

 

History

History
5 lines (4 loc) · 1.36 KB

File metadata and controls

5 lines (4 loc) · 1.36 KB

King Escape Editorial

The basic premise of the problem is that the king must make it to a certain square on the chessboard, while avoiding running into a square the queen is controlling. This calls for a simple DFS (ish) logic, where we can start from the king's coordinate and launch a full-scale DFS on all the squares the king can reach to attempt to reach the final square. So, our only real problem would be to check if the current square is controlled by the queen or not. The first two conditions are easy: the king must not be on the same row or column, but the diagonal condition is a bit harder. The easiest way to think about it is that the absolute value of the difference of the x coordinates of the king and the queen must match the absolute value of the difference of the y coordinates of the king and the queen. Once we have this figured out, it's easy: just launch a DFS from the square the king is on, do the premilinary checks for the current square, and launch more DFS's every square the king might be able to go to, which is 8 total.

Time Complexity

Since we only launch the DFS once, and it goes through the array only once, the program has a time complexity of O(n^2). This time complexity usually is a problem, but since n is only 1000 maximumum, which means O(n^2) is 10^6 maximum, it's way under the TLE zone of roughly 10^8 operations per second.