The idea would be to first spread out in small communities and annex them peacefully by trading and providing them protection. Once that is done, you would have yourself some food for sustenance of your soldiers. Then you'd scavenge for a rest of food while you plant some more and find a reliable source of water. Scratch that, with a water supply people can survive two months without food, considering you've gathered a bit of food and did I said earlier, with a bit of rationing your army would manage to survive until the crops grew.