洪水填充_洪水填充+算法+c++

题目描述
在一个nxm矩阵形状的城市里爆发了洪水，洪水从(0,0)的格子流到这个城市，在这个矩阵中有的格子有一些建筑，洪水只能在没有建筑的格子流动。请返回洪水流到(n - 1,m - 1)的最早时间(洪水只能从一个格子流到其相邻的格子且洪水单位时间能从一个格子流到相邻格子)。
给定一个矩阵map表示城市，其中map[i][j]表示坐标为(i,j)的格子，值为1代表该格子有建筑，0代表没有建筑。同时给定矩阵的大小n和m(n和m均小于等于100)，请返回流到(n - 1,m - 1)的最早时间。保证洪水一定能流到终点。

注意这不是那个简单的动态规划，而是可以往回走的，可以用队列来实现四个方向的迭代搜索

class Flood {
public:
    int floodFill(vector<vector<int> > map, int n, int m) {
        // write code here
        int direction[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
        queue<int> q;
        q.push(0);
        while(!q.empty()){
            int cur=q.front();
            q.pop();
            int i=cur/m;   //得出x轴坐标
            int j=cur%m;   //得出y轴坐标
            if(i==n-1 && j==m-1){
                return map[n-1][m-1];
            }
            for(int k=0;k<4;k++){
                int next_x=i+direction[k][0];
                int next_y=j+direction[k][1];
                if(next_x>=0 && next_x<n && next_y>=0 && next_y<m && map[next_x][next_y]==0){
                    q.push(next_x*m+next_y);
                    map[next_x][next_y]=map[i][j]+1;
                }
            }
        }
        return 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Flood {
public:
    int floodFill(vector<vector<int> > map, int n, int m) {
        // write code here
        int x,y,point;
        int direction[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
        queue<int> q;
        q.push(0);
        int next_x,next_y;

        if(n==0 || m==0 ||map[0][0]) return -1;

        while(!q.empty())
           {
             point = q.front();
             q.pop();
             x = point/m;
             y = point%m;
            if(x==n-1 && y == m-1)
                break;
            for(int k=0;k<4;k++)
               {
                next_x = x + direction[k][0];
                next_y = y + direction[k][1];
                if(next_x >=0 &&next_x <n && next_y >=0 && next_y <m && map[next_x][next_y] == 0)
                    {
                    q.push(next_x *m+next_y);
                    map[next_x][next_y] = map[x][y] +1;
                }
            }

        }
        return map[n-1][m-1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36