Having no defined starting cell, how to find the two farthest cells in a grid with obstacles (walls and such) in the most efficient way?
Doesn't need to be a perfect result, can be an approximation, given it's good enough.
If you know how, I love you.
To minimize the amount of deadends append first the cardinals to the queue and then the primary intercardinals (diagonals). Also keep track of the last deadend and if you find a new deadend too close to the last you delete the last and keep the new found one. In large maps you can also calculate the Manhattan distance from the deadend to the center of the map and if it's too short you just don't add the deadend.
Since you test each path twice (p1 to p2 then p2 to p1) once you test p1 to p2 you can also register p2 to p1 off the bat with the same distance to halve the amount of times you need to do an A* search. The times you need to do an A* search then can be calculated by number of deadends * (number of deadends - 1) / 2.