Representation of state space, action space and reward system for RL porblem
I would suggest you to use Deep Q or A2C (I personally use A2C). As a terminal state you can consider the state in which every tile has been visited once, except if you want to your agent wonder forever. I create OpenAI gym gridworlds so I can use some of their very useful wrappers (example TimeLimit wrapper in which an episode terminates when a certain number of steps has been reached).

For your state representation I would suggest you to follow  well established practices. I assume that you want to use CNNs as a perceptual module and not MLP. You could either use an image of your gridworld with different colors for every entity or use what we call feature-image layers as inputs. These are simply a volume of images and each image has the same dimensions as your grid map and is everywhere 0 except the location of an entity which will have a value of 1. This is in other words a one-hot encoding but in the spatial dimensions of your map.

Actions seem fine to me and your reward function is worth giving a try but I wouldn't penalize that heavily (maybe -0.1 instead of -0.75). The issue will rise initially when your agent explores. If it is heavily penalized it will try to maintain its reward and deliberately crash.

Do not get frustrated if initially it doesn't learn. Designing a proper reward function is quite a task besides the proper feature representation (I suggest images).