面试题.... 不会写，求指教

一个2d array里面，给起点和终点，
1是墙，0是房间，返回是否能够经过所有房间之下到达终点。

起初思路是写DFS，但写了一下卡住了不会写，求大神解答，可以给大米！ ！谢谢!!

example:
101111
100011
000011
000001

start is 0,0

end is 3,5

return True

用C++試著寫了一個暴力解法
不過複製vector會花掉很多時間
求大神改良

思路是DFS+concurrency
把走過的路變成1存在新地圖傳下去
比較0的數目與走的步數是否相等

1. void m(vector<bool>& maze, int cx, int cy, int edx, int edy, int xlen, int ylen, int& path, int& t, bool &ret){
   
2.     vector<bool> nmaze = maze;
   
3.     if(!ret)
   
4.         if(cx == edx && cy == edy && path == t) ret = true;
   
5.         else{
   
6.             ++path;
   
7.             nmaze[cx*ylen+cy] = 1;
   
8.             if(cx-1 != -1   && !maze[(cx-1)*ylen+cy]) m(nmaze, cx-1, cy  , edx, edy, xlen, ylen, path,t, ret);
   
9.             if(cx+1 != xlen && !maze[(cx+1)*ylen+cy]) m(nmaze, cx+1, cy  , edx, edy, xlen, ylen, path,t, ret);
   
10.             if(cy-1 != -1   && !maze[(cx)*ylen+cy-1]) m(nmaze, cx  , cy-1, edx, edy, xlen, ylen, path,t, ret);
    
11.             if(cy+1 != ylen && !maze[(cx)*ylen+cy+1]) m(nmaze, cx  , cy+1, edx, edy, xlen, ylen, path,t, ret);
    
12.         }
    
13. }
    
14. int main()
    
15. {
    
16.     int xlen, ylen, i, j, stx, sty, edx, edy, path = 0, total = 0;
    
17.     vector<bool> maze;
    
18.     bool tmp, ret = false;
    
19. 
    
20.     cin >> xlen;
    
21.     cin >> ylen;
    
22.     for(i = 0; i != xlen; ++i){
    
23.         for(j = 0; j != ylen; ++j){
    
24.             cin >> tmp;
    
25.             if(!tmp) ++total;
    
26.             maze.push_back(tmp);
    
27.         }
    
28.     }
    
29.     cin >> stx;
    
30.     cin >> sty;
    
31.     cin >> edx;
    
32.     cin >> edy;
    
33.     m(maze, stx, sty, edx, edy, xlen, ylen, path, total, ret);
    
34.     if(ret) cout << "true";
    
35.     else cout << "false";
    
36. }

复制代码

T大农民伯伯 发表于 2018-10-26 11:04
题目描述不清楚，允不允许一个格子踩多遍，允许的话找要求所有的格子在一个连通块里。不允许的话感觉是个超 ...

不允许的，所以感觉union find不能用

2d array大小限制有阀？

这种差不多就是一路dfs走到底了。。 如果n不算太大 stack space没毛病就行。

但是如果n很大的话这个你就不好说了。。

你这个例子从墙开始…

nlackx 发表于 2018-10-26 00:59
你这个例子从墙开始…

那我換成:
301111
100011
000011
000005

我自己寫了個dfs，但tle了....

先 check start 和 end， 两者都必须是0， 否则false
然后Union find, 所有房间（0） 都必须在一个group里， 否则false

题目描述不清楚，允不允许一个格子踩多遍，允许的话找要求所有的格子在一个连通块里。不允许的话感觉是个超难的问题。

这是在求Hamiltonian path 么。。。。貌似是np complete。。。

不允许的话我能想到的应用场景应该是谷歌经典的扫地机器人了，为了扫地效率不走回头路。