There is a row of N walls in Geeksland. The king of Geeksland ordered Alexa to color all the walls
on the occasion of New Year. Alexa can color each wall with one of the K colors. The cost
associated with coloring each wall with a particular color is represented by a 2D costs array of
size N * K. For example, costs[0][0] is the cost of coloring wall 0 with color 0; costs[1][2] is the cost
of coloring wall 1 with color 2, and so on... Find the minimum cost to color all the walls.
You need to nd the minimum cost to paint all the walls such that no two adjacent walls have the
same color.
Example 1:
Input:
N = 4, K = 3
costs[][] = {{1, 5, 7},
{5, 8, 4},
{3, 2, 9},
{1, 2, 4}}
Output:
8
Explanation:
Paint wall 0 with color 0. Cost = 1
Paint wall 1 with color 2. Cost = 4
Paint wall 2 with color 1. Cost = 2
Paint wall 3 with color 0. Cost = 1
Total Cost = 1 + 4 + 2 + 1 = 8
-----------
这道题有两种做法,一种是dfs,一种是bfs,dfs我是参考的其他人的做法,一开始没想到,就是2次dfs,到左下如果可以就是true,到右上如果可以也是true,返回返回2个数组都是true的情况,那么就是能同时到2个地方。但是这样一想,不就是可以bfs吗,先把边缘的地方放到队列中,然后bfs就行,只是要bfs2次。然后查看2个数组都是true的情况即可。
dfs的代码:
下面是dbfs的代码,个人觉得bfs还好点,而且我自己写出来的。。。