给定一个n乘m的矩阵map,其中map[i][j]表示坐标为(i,j)的格子,值为1代表该格子不能通过,0代表可以通过。现从(0,0)的格子走到(n - 1,m - 1),单位时间只能走一格,不能途径无法通过的格子,请返回最短时间。同时给定矩阵的大小n和m(n和m均小于等于100),并且一定能走到终点。
/* 四个方向遍历搜索,用递归始终是超时,后来参考网上其他大神的方法,用队列来实现四个方向的迭代搜索。 */ 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; } }