首页 > 试题广场 > 走格子
[编程题]走格子
  • 热度指数:8835 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

给定一个n乘m的矩阵map,其中map[i][j]表示坐标为(i,j)的格子,值为1代表该格子不能通过,0代表可以通过。现从(0,0)的格子走到(n - 1,m - 1),单位时间只能走一格,不能途径无法通过的格子,请返回最短时间。同时给定矩阵的大小nm(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;
                }
            }
        }
    }
};

发表于 2015-09-05 18:50:37 回复(6)
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;
        }
    }
编辑于 2016-08-22 11:35:14 回复(5)
并没有什么骚操作,老老实实按照题目描述的来做。
把建筑全部换成-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;
    }
};

发表于 2017-08-09 15:23:39 回复(1)
import java.util.*;
/*
思路:这种求要走多少步的题目而不是求有多少种方法的题目我倒是第一次见
然后我就试试。怎么就通过了呢- - BFS我学的不好,再去学学
*/
public class Flood {
    public int floodFill(int[][] map, int n, int m) {
     return m+n-2;
    }
}

发表于 2017-06-29 21:23:40 回复(7)
需要考虑一个回流问题,所以四个方向都有可能
**这是错误的解法**, 只是刚好测试数据通过了
# -*- 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

编辑于 2016-09-18 20:32:44 回复(5)
BFS算法 
class Flood {
public:
int floodFill(vector<vector<int> > map, int n, int m) {
if (map.size() == 0 || map[0].size() == 0)
return 0;
queue<pair<int, int>>q;
q.push(pair<int,int>(0,0));
pair<int, int>p;
int x, y;
while (!q.empty())
{
p = q.front();
q.pop();
x = p.first;
y = p.second;
if (x == n - 1 && y == m - 1){
return map[x][y];
}
if (x + 1 < n&&map[x+1][y]==0){
q.push(pair<int,int>(x+1,y));
map[x + 1][y] = map[x][y] + 1;
}

if (x - 1 >= 0&&map[x-1][y]==0){
q.push(pair<int, int>(x - 1, y));
map[x - 1][y] = map[x][y] + 1;
}

if (y + 1 < m&&map[x][y+1]==0){
q.push(pair<int,int>(x,y+1));
map[x][y + 1] = map[x][y] + 1;
}

if (y - 1 >= 0&&map[x][y-1]==0){
q.push(pair<int, int>(x, y - 1));
map[x][y - 1] = map[x][y] + 1;
}
}
}
};



0, 0, 1, 0
1, 0, 1, 0
0, 0, 1, 0
0, 1, 0, 0
0, 0, 0, 0  可以通过  
发表于 2015-09-11 11:59:16 回复(1)
//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));
                }
            }
        }
    }
};

发表于 2019-06-23 20:42:51 回复(0)
class Flood {
public:
    //使用广度优先遍历+数组存储移动距离(动态规划)
    class Point{//定义节点类,包含某一个点的横纵坐标,这样定义是为了标记已经走过的节点
        public:
        int x;
        int y;
        Point(int a,int b):x(a),y(b){}
    };
    int floodFill(vector<vector<int> > map, int n, int m) {
        //使用广度优先遍历
        if(map.size()==0||map[0].size()==0) return 0;//程序鲁棒性
        queue<Point> res;//定义BFS队列
        res.push(Point(0,0));//将入口点写入队列
        int x,y;
        map[0][0]=0;//
        while(!res.empty())//当队列不为空时(广度优先遍历,将当前节点的相邻节点写入队列)
            {
            Point cur=res.front();
            x=cur.x;
            y=cur.y;
            if(x==n-1&&y==m-1) return map[n-1][m-1];//返回到终点时的值
            //以下内容是广度优先遍历,插入队列的顺序依次是右、下、左、上,
            //只要满足这个插入顺序,就能保证最后找到的点事最快找到的,因为出口的位置在右下角
            //另外,虽然是按广度优先(层序)遍历,每一层级的节点的时间值只是上一层加1,因此实际的时间累加值是深度优先的。
            if(y+1<m&&map[x][y+1]==0)
                    
                {
                    res.push(Point(x,y+1));
                     map[x][y+1]=map[x][y]+1;
                }
                if(x+1<n&&map[x+1][y]==0)
                {
                    res.push(Point(x+1,y));
                    map[x+1][y]=map[x][y]+1;
                }
                
                 if(y-1>=0&&map[x][y-1]==0)
                {
                    res.push(Point(x,y-1));
                     map[x][y-1]=map[x][y]+1;
                }
                if(x-1>=0&&map[x-1][y]==0)
                {
                    res.push(Point(x-1,y));
                    map[x-1][y]=map[x][y]+1;
                }
            
            res.pop();  
        }
        return 0;
    }
};
发表于 2017-04-09 17:29:59 回复(0)
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];
    }
}

发表于 2017-06-27 18:37:36 回复(2)
class Flood {
public:
    int floodFill(vector<vector<int> > map, int n, int m) {
        return m+n-2;
    }
};
发表于 2017-03-19 18:15:37 回复(6)
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向负数进军

发表于 2020-04-07 13:02:25 回复(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];
    }
};

发表于 2020-01-06 21:01:01 回复(0)
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;
    }
};

发表于 2019-03-02 02:16:42 回复(0)
层次遍历

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;
    }
};


编辑于 2018-12-29 12:08:20 回复(0)
用队列,对每个格子的上下左右位置进行标记。
数据结构中对图的遍历也使用过队列的方法。
时间复杂度就是最短路径的长度
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];
    }

编辑于 2018-10-31 18:22:43 回复(0)
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]; 
    }
}

发表于 2017-08-12 10:02:11 回复(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;
    }

编辑于 2016-09-08 10:26:26 回复(0)
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]; 
    }
};

发表于 2016-08-17 20:29:23 回复(4)
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));
	}
}




发表于 2016-04-25 16:48:58 回复(0)
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;
    }
}

发表于 2015-11-10 14:39:55 回复(1)

问题信息

难度:
73条回答 13444浏览

热门推荐

通过挑战的用户

查看代码