Cat food "for catching insects" is probably much better than searching under rocks. If I had no other means, I would try giving mantids cat food temporarily, rather than have them starve.
I have fed mantids Pycnoscelus surinamensis roaches from under debris, and even cultured them for a while, as feeders(feeding them sweet friuts and veggies so they won't be full of decaying wood and plants). But...
most of the bugs that are found under rocks might taste bad and be full of dirt and decaying plant material. I have never heard of mantids looking for food under rocks. They will eat it, but you may be able to do better for them with ease. My mantids would always eat around the dirt ball in the guts of these insects, but usually finish flying insects, or roaches that have a sweet filling.
Flying insects are most likely much tastier and closer to what they get in the wild.
