In this paper, we propose a method of reconfiguring two-dimensional meshes embedded in hypercubes. Our reconfiguration for link failures consists of two stages. The first one assigns d dimensions of hypercubes to two directions with respect to rows and columns in the mesh so that the number of disconnected pairs with adjacent rows and columns becomes smaller. The second one reestablishes the mesh communication by assigning Cartesian product of two Gray code sequences, which represent the order of healthy rows and columns to every node. We introduce the graphs with edges corresponding to connections between rows or columns, and search the sequences. Then either approach based on depth-first search or the one based on genetic algorithm is applied to the graphs. The above is valid for node failures by regarding a faulty node as a node without healthy links. The simulation results show that our method reconfigures embedded meshes efficiently with relatively short computation time.