P1859 Disobedient Robot

The robot receives $N$ commands, but it does not want to move onto an obstacle or go out of bounds, so it decides to refuse some commands. Find the minimum number of commands it must refuse. `FORWARD` move forward by 1. `BACK` move backward by 1. `LEFT` turn left by 90 degrees. `RIGHT` turn right by 90 degrees. Initially, the robot is facing upwards.

The first line contains $M,N,X_0,Y_0$ ($M \le 100, N \le 1000$), meaning the field size is $M\times M$, there are $N$ commands in total, and the starting point is $(X_0,Y_0)$. Next is an $M\times M$ matrix representing the field. Here `.` denotes an empty cell, and `*` denotes an obstacle. Then follow $N$ lines, each representing one command.

Output a single integer: the minimum number of commands to refuse.

Translated by ChatGPT 5