走格子

/*
四个方向遍历搜索，用递归始终是超时，后来参考网上其他大神的方法，用队列来实现四个方向的迭代搜索。
*/
class Flood {
public:
    int floodFill(vector<vector<int> > map, int n, int m) {
        // write code here
        if(n == 0||m == 0|| map[0][0]) return 0;
        queue<int> qRecord;
        int direction[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
        int x,y,next_x,next_y;
        int point;
        int k;
        qRecord.push(0);
        while(!qRecord.empty()){
            point = qRecord.front();
            qRecord.pop();
            x = point/m;
            y = point%m;
            if((x+1) == n && (y+1) == m){
                return map[n-1][m-1];
            }
            for(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){
                    qRecord.push(next_x*m+next_y);
                    map[next_x][next_y] = map[x][y] + 1;
                }
            }
        }
    }
};

import java.util.*;

//使用DFS来解决
public class Flood {
    public int floodFill(int[][] map, int n, int m) {
        // write code here
        if(m==0||map[0].length==0){
            return 0;
        }
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(0,0));
        Point p;
        int x,y;
        while(!queue.isEmpty()){//QUEUE中存储的是一个点的邻接点
            p = queue.poll();
            x = p.x;
            y = p.y;
           		
            if (x == n - 1 && y == m - 1){//如果得到结果，直接返回
                return map[x][y];
			}
			if (x + 1 < n&&map[x+1][y]==0){//右边的节点可以走，
				queue.add(new Point(x+1,y));//将右边节点加入队列
				map[x + 1][y] = map[x][y] + 1;//初始化右边节点。注意，我们这里判断的条件是map[x+1][y]==0，也就是说路是通的。另一层含义是如果不是0，说明走过了或者有障碍（是1）
			}
            
            			
            if (y + 1 < m&&map[x][y+1]==0){//下面的节点，这里顺序不能变，因为最早时间，肯定是从右边或者下面走，只有走不通的时候才走左边和上面
				queue.add(new Point(x,y+1));
				map[x][y + 1] = map[x][y] + 1;
			}

			if (x - 1 >= 0&&map[x-1][y]==0){//同理左边节点
				queue.add(new Point(x - 1, y));
				map[x - 1][y] = map[x][y] + 1;
			}

			if (y - 1 >= 0&&map[x][y-1]==0){//上面的节点
				queue.add(new Point(x, y - 1));
				map[x][y - 1] = map[x][y] + 1;
			}
        }
        
        return 0;
    }
}
    
     
class Point{
    int x;
    int y;
    public Point(int x,int y){
        this.x=x;
        this.y=y;
        }
    }

并没有什么骚操作，老老实实按照题目描述的来做。
把建筑全部换成-1，正数用来记录洪水到达每个点的时间。
每一次循环都寻找上一个时间点被淹没的点，寻找这个点周围仍然为0并且没有建筑的地方，填上新的时间点。
直到最后一个格子被淹没

class Flood {
public:
    int floodFill(vector<vector<int> > map, int n, int m) {
        // write code here
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(map[i][j]==1)map[i][j]=-1;
        map[0][0]=1;
        int count=1;
        while(map[n-1][m-1]==0){
            for(int i=0;i<n;i++)
            	for(int j=0;j<m;j++){
                    if(map[i][j]==count){
                        if(i!=0)
                            if(map[i-1][j]==0)map[i-1][j]=count+1;
                        if(i!=n-1)
                           if(map[i+1][j]==0)map[i+1][j]=count+1;
                        if(j!=0)
                           if(map[i][j-1]==0)map[i][j-1]=count+1;
                        if(j!=m-1)
                           if(map[i][j+1]==0)map[i][j+1]=count+1;
                    }
                }
            count++;
        }
        return count-1;
    }
};

# -*- coding:utf-8 -*-
class Flood:
    def floodFill(self, tmap, n, m):
        dp = [[10000000] * (m + 2) for i in range(n + 2)]
        dp[1][1] = 0
        
        for i in range(n):
            for j in range(m):
                if i == 0 and j == 0: continue
                if tmap[i][j] == 0:
                    dp[i + 1][j + 1] = min(dp[i][j + 1], dp[i + 1][j],
                                          dp[i + 2][j + 1], dp[i + 1][j + 2]) + 1
                    
        return dp[n][m]

# -*- coding:utf-8 -*-

from collections import deque
class Flood:

    def floodFill_bfs(self, tmap, n, m):
        queue = deque()
        queue.append((0, 0))
        distance = {}
        distance[(0, 0)] = 0
        self.n = n
        self.m = m
        self.tmap = tmap

        while queue:
            cur = queue.popleft()
            for next in self.graphNeighbors(cur):
                if next not in distance:
                    queue.append(next)
                    distance[next] = 1 + distance[cur]

        return distance[(n - 1, m - 1)]

    def graphNeighbors(self, point):
        i = point[0]
        j = point[1]
        neighbors = []

        if 0 <= i - 1 < self.n and self.tmap[i - 1][j] == 0:
            neighbors.append((i - 1, j))
        if 0 <= i + 1 < self.n and self.tmap[i + 1][j] == 0:
            neighbors.append((i + 1, j))
        if 0 <= j - 1 < self.m and self.tmap[i][j - 1] == 0:
            neighbors.append((i, j - 1))
        if 0 <= j + 1 < self.m and self.tmap[i][j + 1] == 0:
            neighbors.append((i, j + 1))

        return neighbors

BFS算法 

//bfs
class Flood {
public:
    int visited[102][102]={0};
    int offset[4][2]={1,0,0,1,-1,0,0,-1};
    int floodFill(vector<vector<int> > map, int n, int m) {
        int step=0;
        bfs(map,n,m,step);
        return step;
    }
private:
    void bfs(vector<vector<int> >&map,int &n,int &m,int &step)
    {
        queue<pair<int,int> >q;
        q.push(pair<int,int>(0,0));
        while(!q.empty())
        {
            ++step;
            int size=q.size();
            for(int i=0;i<size;++i)
            {
                pair<int,int>f=q.front();
                q.pop();
                visited[f.first][f.second]=1;
                for(int i=0;i<4;++i)
                {
                    int tx=f.first+offset[i][0];
                    int ty=f.second+offset[i][1];
                    if(tx==n-1&&ty==m-1) return ;
       if(tx<0||tx>=n||ty<0||ty>=m||map[tx][ty]==1||visited[tx][ty]==1)
                        continue;
                    q.push(pair<int,int>(tx,ty));
                }
            }
        }
    }
};

    //使用广度优先遍历+数组存储移动距离（动态规划）

import java.util.*;

public class Flood {
//由题意求最短时长，那么确定不回流，水只能向下，向右走
    public int floodFill(int[][] map, int n, int m) {
        // write code here
        int data[][]=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                data[i][j]=Integer.MAX_VALUE;
            }
        }
        data[0][0]=0;
        for(int i=1;i<n;i++){
            if(map[i][0]==0){
                data[i][0]=data[i-1][0]+1;
            }else{
                break;
            }
        }
        for(int i=1;i<m;i++){
            if(map[0][i]==0){
                data[0][i]=data[0][i-1]+1;
            }else{
                break;
            }
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                if(map[i][j]==0){
                    if(data[i-1][j]!=Integer.MAX_VALUE || data[i][j-1]!=Integer.MAX_VALUE){
                        data[i][j]=Math.min(data[i-1][j],data[i][j-1])+1;
                    }
                }
            }
        }
        return data[n-1][m-1];
    }
}

class Flood {
public:
    int floodFill(vector<vector<int> > map, int n, int m) {
        return m+n-2;
    }
};

using Coordinate = pair<int, int>;

class Flood {
public:
  int floodFill(vector<vector<int>> map, int n, int m) {
    
    queue<Coordinate> q;
    q.emplace(0, 0);
    map[0][0] = 1;
    
    static const array<int, 5> dirs { 0, -1, 0, 1, 0 };
    
    int steps = 0;
    while (not q.empty()) {
      size_t s = q.size();
      while (s--) {
        const auto [x, y] = q.front(); q.pop();
        if (x == m - 1 && y == n - 1) return steps;
        for (int i = 0; i < 4; ++i) {
          const int nx = x + dirs[i], ny = y + dirs[i + 1];
          if (nx < 0 || nx == m || ny < 0 || ny == n || map[ny][nx])
            continue;
          q.emplace(nx, ny);
          map[ny][nx] = 1;
        }
      }
      ++steps;
    }
    
    return steps;
  }
};

class Flood {
public:
    int floodFill(vector<vector<int> > map, int n, int m) {
        // write code here
        return min_step(0,0,map,n,m);
    }
    int min_step(int i,int j,vector<vector<int> >& map,int n,int m)
    {
        if(i==n-1&&j==m-1)
            return 0;
        else if(i>-1&&i<n&&j>-1&&j<m&&map[i][j]==0)
        {
            return 1+min(min_step(i+1,j,map,n,m),min_step(i,j+1,map,n,m));
        }
      else
         return 10000;
        
                         
    }
    int min(int a,int b)
    {
        return a<b?a:b;
    }
                         
   
};//递归版,(0,0)可以看作(0,1)+1和(1,0)+1的最短路径，不通的路返回一个大值。
class Flood {
public:
    int floodFill(vector<vector<int> > map, int n, int m) {
        // write code here
        vector<vector<int> > record(n+1,vector<int>(m+1,10000));
        record[0][1]=-1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(map[i-1][j-1]==1)
                    continue;
                else
                  record[i][j]=1+min(record[i][j-1],record[i-1][j]);
              }
        }
        return record[n][m];
    }
   };//动态规划先构建一个全为10000的二维数组，刚刚开始给个启动值-1，保证出发点步数是0
class Flood {
public:
    int floodFill(vector<vector<int> > map, int n, int m) {
        // write code here
        //vector<vector<int> > record(n+1,vector<int>(m+1,10000));
        //record[0][1]=-1;
        for(int i=1;i<n;i++)
        {
            if(map[i-1][0]==1||map[i][0]==1)
                map[i][0]=1;
            else map[i][0]=map[i-1][0]-1;
        }
        for(int i=1;i<m;i++)
        {
            if(map[0][i-1]==1||map[0][i]==1)
                map[0][i]=1;
            else map[0][i]=map[0][i-1]-1;
        }
        for(int i=1;i<n;i++)
        {
            for(int j=1;j<m;j++)
            {
                if(map[i][j]>0)
                    continue;
                else
                  map[i][j]=-1+min(map[i][j-1],map[i-1][j]);
              }
        }
        return -map[n-1][m-1];
    }
    int min(int a,int c)
    {
        int max=a>c?a:c;
        if(a>0&&c>0)
            return a+c;
        
        else if(max>0)
            return a+c-max;
        else
            return max;
    }
   };
//不用空间的动态，不把1变-1直接把0向负数进军

class Flood {
public:
    int floodFill(vector<vector<int> > map, int n, int m) {
        // write code here
        //动态规划
        /*
        1. 先填满最大值
        2. 第一行只能从左到右re[0][i]=re[0][i-1]+1，第一列只能从上到下re[j][0]=re[j-1][0]+1
        3. 其他空格 可以从上方到达，也可以从左方到达re[i][j]=min(re[i-1][j],re[i][j-1])+1
        */
        vector<vector<int>>re;
        for (int i=0;i<n;i++)
        {
            vector<int>tmp;
            for (int j=0;j<m;j++)
                tmp.push_back(INT_MAX);
            re.push_back(tmp);
        }
        
        re[0][0]=0;
        
        for (int i=1;i<n;i++)
        {
            if(map[i][0]==0)
                re[i][0]=re[i-1][0]+1;
            else
                break;
        }

        for(int j=1;j<m;j++)
        {
            if (map[0][j]==0)
                re[0][j]=re[0][j-1]+1;
            else
                break;
        }

        for (int i=1;i<n;i++)
            for (int j=1;j<m;j++)
                if(map[i][j]==0)
                    if(re[i-1][j]!=INT_MAX||re[i][j-1]!=INT_MAX)
                        re[i][j]=min(re[i-1][j],re[i][j-1])+1;
        
        return re[n-1][m-1];
    }
};

class Flood {
public:     struct P{         int x,y,t;         P(int x,int y,int t):x(x),y(y),t(t){}     };
    int floodFill(vector<vector<int> > map, int n, int m) {
        bool vis[n][m];
        memset(vis,false,sizeof(vis));
        int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
        queue<P> q;
        q.push(P(0,0,0));
        while(!q.empty()){
            P p = q.front();
            q.pop();
            if(p.x==n-1 && p.y==m-1)
                return p.t;
            vis[p.x][p.y] = true;
            for(int i=0;i<4;i++){
                int x = p.x + dir[i][0];
                int y = p.y + dir[i][1];
                int t = p.t + 1;
                if(x>=0 && x<n && y>=0 && y<m && map[x][y]==0 && !vis[x][y])
                    q.push(P(x,y,t));
                                 }         }
        return -1;
    }
};

class Flood {
public:
    int floodFill(vector<vector<int> > map, int n, int m) {
        queue<vector<int> > Q;
        map[0][0] = -1;
        Q.push(vector<int>{0, 0});
        int t = -1;
        while (!Q.empty()) {
            int sz = Q.size();
            ++t;
            while (sz--) {
                vector<int> p = Q.front();
                Q.pop();
                if (p[0] == n-1 && p[1] == m-1) { return t; }
                vector<vector<int> > pos = vector<vector<int> >{{p[0] - 1, p[1]}, {p[0] + 1, p[1]}, {p[0], p[1] - 1}, {p[0], p[1] + 1}};
                for (auto pp : pos) {
                    if (pp[0] >= 0 && pp[0] < n && pp[1] >= 0 && pp[1] < m && map[pp[0]][pp[1]] == 0) {
                        map[pp[0]][pp[1]] = -1;
                        Q.push(vector<int>{pp[0], pp[1]});
                    }
                }
            }
        }
        return -1;
    }
};

int floodFill(vector<vector<int> > map, int n, int m) {
        // write code here
        queue<int>step;
        step.push(0);step.push(0);
        while(!step.empty()&&(!map[n-1][m-1])){
            int i=step.front();step.pop();
            int j=step.front();step.pop();
            if((i>0)&&(!map[i-1][j])){
                map[i-1][j]=map[i][j]+1;
                step.push(i-1);step.push(j);
            }
            if((i<n-1)&&(!map[i+1][j])){
                map[i+1][j]=map[i][j]+1;
                step.push(i+1);step.push(j);
            }
            if((j>0)&&(!map[i][j-1])){
                map[i][j-1]=map[i][j]+1;
                step.push(i);step.push(j-1);
            }
            if((j<m-1)&&(!map[i][j+1])){
                map[i][j+1]=map[i][j]+1;
                step.push(i);step.push(j+1);
            }
            
        }
        return map[n-1][m-1];
    }

import java.util.*;

public class Flood {
    public int floodFill(int[][] map, int n, int m) {
        // write code here
        //思路：使用bfs，用两个队列分别存放x和y坐标。
        //每次从队列中取出当前格子点，然后对它可以流向的四个方向进行判断，
        //如果可以流加入队列。
        
            if(m==0||n==0)
                return 0;  
            int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}};//上下左右四个方向流动  
              
            Queue<Integer> qx = new LinkedList<>();  
            Queue<Integer> qy = new LinkedList<>();   
            map[0][0]=0;  
            qx.offer(0);  
            qy.offer(0); 
        
            while(!qx.isEmpty()){  
                int x = qx.poll();  
                int y = qy.poll();  
                  
                if(x==n-1 && y==m-1)
                    return map[n-1][m-1];  
                  
                for(int i=0; i<4; i++){  //四个方向进行判断，能走的加入队列
                    int nextx = x + dir[i][0];  
                    int nexty = y + dir[i][1];  
                    if(nextx >=0 && nextx <n && nexty >=0 && nexty <m && map[nextx][nexty]==0){  
                        map[nextx][nexty] = map[x][y] + 1;  
                        qx.offer(nextx);  
                        qy.offer(nexty);  
                    }  
                } 
            }
            return map[n-1][m-1]; 
    }
}

//未添加栅栏,做检测较为啰嗦
    public int floodFill(int[][] map, int n, int m) {
        int dp[][] = new int[n][m], max = n * m;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dp[i][j] = max;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                f(map, n, m, dp, max, i, j);
            }
            for (int j = m - 1; j >= 0; j--) {  //解决回流问题
                f(map, n, m, dp, max, i, j);
            }
        }

        return dp[n - 1][m - 1];
    }

    private void f(int[][] map, int n, int m, int[][] dp, int max, int i, int j) {
        if (i == 0 && j == 0) {
            dp[i][j] = 0;
            return;
        }
        if (map[i][j] == 1) {
            return;
        }
        int t = max;
        if (i >= 1 && map[i - 1][j] == 0)
            t = dp[i - 1][j];
        if (j >= 1 && map[i][j - 1] == 0)
            t = Math.min(t, dp[i][j - 1]);
        if (i < n - 1 && map[i + 1][j] == 0)
            t = Math.min(t, dp[i + 1][j]);
        if (j < m - 1 && map[i][j + 1] == 0)
            t = Math.min(t, dp[i][j + 1]);
        dp[i][j] = t + 1;
    }

//添加栅栏
    import static java.lang.Math.min;

    public int floodFill(int[][] map, int n, int m) {
        int dp[][] = new int[n + 2][m + 2], max = n * m;
        for (int i = 0; i < n + 2; i++) {
            Arrays.fill(dp[i], max);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0, delta = 1; j >= 0; j+=delta) {
                f(map, dp, i, j);
                if (j == m - 1)
                    delta *= -1;
            }
        }

        return dp[n][m];
    }

    private void f(int[][] map, int[][] dp, int i, int j) {
        if (i == 0 && j == 0) {
            dp[i + 1][j + 1] = 0;
            return;
        }
        if (map[i][j] == 1) {
            return;
        }
        dp[i + 1][j + 1] = min(dp[i][j + 1], min(dp[i + 1][j + 2], min(dp[i + 2][j + 1], dp[i + 1][j]))) + 1;
    }

class Flood {
public:
    int floodFill(vector<vector<int> > map, int n, int m) {
        // write code here
        if(n<=0 || m<=0) return -1;
        if(map[0][0]==1) return -1;
        int MAX=100000;
        vector<vector<int> >vec(n+2,vector<int>(m+2,MAX));
        vec[1][1]=0;
        //处理
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(i==0&&j==0) continue;
                if(map[i][j]==0)
                {
                    vec[i+1][j+1]=min(min(vec[i][j+1],vec[i+1][j]),min(vec[i+2][j+1],vec[i+1][j+2]))+1;
                }
            }
        }
       return vec[n][m]; 
    }
};

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class HongShui {
	public static class MyPoint{
		int x;
		int y;
		public MyPoint(int x,int y){
			this.x=x;
			this.y=y;
		}
	}
	
	public static void print(int[][]map){
		for(int i=0;i<map.length;i++){
			for(int j=0;j<map[0].length;j++){
				System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}
		System.out.println();
	}
	
	  public static int floodFill(int[][] map, int n, int m) {
	        // write code here
		  int visited[][]=new int[n][m];
		  int road[][]=new int[n][m];
		  int direction[][]=new int[][]{{1,0},{0,1},{0,-1},{-1,0}};
		  Queue<MyPoint>q=new LinkedList<MyPoint>();
		  MyPoint start=new MyPoint(0, 0);
		  visited[start.x][start.y]=1;
		  q.add(start);
		  while(!q.isEmpty()){
			  MyPoint temp=q.poll();
			  if(temp.x==n-1&&temp.y==m-1){
				  return road[n-1][m-1];
			  }
			  for(int i=0;i<4;i++){
				  MyPoint go=new MyPoint(temp.x+direction[i][0], temp.y+direction[i][1]);
				  if(go.x>=0&&go.y>=0&&go.x<n&&go.y<m&&visited[go.x][go.y]==0&&map[go.x][go.y]==0){
					  visited[go.x][go.y]=1;
					 // print(road);
					  q.add(go);
					  road[go.x][go.y]=road[temp.x][temp.y]+1;
				  }
			  }
		  }
		  return road[n-1][m-1];
	    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][]map=new int[][]{{0,1,0,0,0},
								{0,1,0,1,0},
								{0,0,0,1,0},
								{0,0,0,1,0}};
		System.out.println(floodFill(map, 4, 5));
	}
}

import java.util.*;

public class Flood {
    public int MAX = 10000;
    public int floodFill(int[][] map, int n, int m) {
        int[][] time = new int[n][m];
        time[0][0] = 0;
        for(int i = 1;i<n;i++){
            if(map[i][0] == 1){
                time[i][0] = MAX;
            }else{
                time[i][0] = time[i-1][0]+1; 
            }
        }
        
        for(int j = 1; j<m; j++){
            if(map[0][j] ==1 ){
                time[0][j] = MAX;
            }else{
                time[0][j] = time[0][j-1]+1;
            }
        }
        
        //不考虑回流的情况，比如从右流到左边的情况
        for(int i=1;i<n;i++){
            for(int j = 1; j<m; j++){
                time[i][j]= min(time[i-1][j]+1,time[i][j-1]+1); 
            }
        }
        return time[n-1][m-1];
    }
    
    int min(int a ,int b){
        return a<=b?a:b;
    }
}