ABO3 oxides with the perovskite-related structures are attracting significant interest due to their promising physical and chemical properties for many applications requiring tunable chemistry, including fuel cells, catalysis, and electrochemical water splitting. Here we report on the crystal structure of the entire family of perovskite oxides with ABO3 stoichiometry, where A and B are Ba, Sr, Mn, Ce. Given the vast size of this chemically complex material system, exploration for stable perovskite-related structures with respect to its constituent elements and annealing temperature is performed by combinatorial pulsed laser deposition and spatially-resolved characterization of composition and structure. As a result of this high-throughput experimental study, we identify hexagonal perovskite-related polytypic transformation as a function of composition in the Ba1-xSrxMnO3 oxides after annealing at different temperatures. Furthermore, a hexagonal perovskite-related polytype is observed in a narrow composition-temperature range of the BaCexMn1-xO3 oxides. In contrast, a tetragonally-distorted perovskite is observed across a wider range of compositions and annealing temperatures in the Sr1-xCexMnO3 oxides. This structure stability is further enhanced along the BaCexMn1-xO3 - Sr1-xCexMnO3 pseudo-binary tie-line at x=0.25 by increasing Ba-incorporation and annealing temperature. These results indicate that the BaCexMn1-xO3 - Sr1-xCexMnO3 pseudo-binary oxide alloys (solid solutions) with tetragonal perovskite structure and broad composition-temperature range of stability are promising candidates for thermochemical water splitting applications.