题解

思路

对红色路线，把进入红格的代价设为 $0$、进入蓝格的代价设为 $1$，则从左上到右下的最短路代价就是这条路线必须染紫的蓝格数；蓝色路线同理。

做法

任意一条连接左上与右下的路径和一条连接右上与左下的路径必然相交。一个同时位于两条路径上的格子，无论原色如何，两种路径的代价之和都恰为 $1$，正好对应把它染成紫色一次；只被一条路径经过的异色格也各贡献一次。因此两条独立最短路的代价之和，恰好等于同时满足两个条件的最少染色数。

两张网格图的边权都只有 $0$ 和 $1$，分别使用 0-1 BFS：沿代价 $0$ 的转移把新状态压入双端队列前端，沿代价 $1$ 的转移压入后端。计算红色的左上到右下最短路与蓝色的右上到左下最短路并相加即可。

复杂度

时间复杂度为 $O(N^2)$，空间复杂度为 $O(N^2)$。