字节跳动2018.10.8笔试地震逃生选择

亦凉 2022-05-08 05:28 144阅读 0赞

### 文章目录 ###

*  题目描述
 *  深度遍历
 *  优化深度递归次数
 *  宽度遍历
 *  宽度遍历优化

# 题目描述 #

![在这里插入图片描述][70]  
**输入-版本一：**  
3  
0,-1,1,0  
0,0,0,-1  
0,-1,0,-1  
1,-1,0,0  
**输入-版本二：**  
3  
0,-1,0,0  
0,1,1,-1  
0,-1,0,-1  
0,-1,0,0

# 深度遍历 #

原来的1和-1都会变成0，原来的0有两种情况，如果这个0与某个1即出口的距离<=k，那么这个0还是0，否则为1。  
建立一个同样的大小的二维数组second（每个元素初值为0），然后对每个1进行最大深度为k的深度遍历，遇到1或者-1就忽略，遇到0就把second里面的对应位置second\[row\]\[column\]赋值为1。  
需要注意每次深度遍历都是独立的，不能说是A开始遍历走过的点，然后B开始遍历就不能A走过的这些点。  
所有深度遍历结束后，second\[row\]\[column\]为1说明这个元素与某个1之间的距离<=k，second\[row\]\[column\]为0说明这个元素与每个1之间的距离都>k。

k  = eval(input())
    li = []#原数组
    exitLi = []#记录出口
    
    def readexit(index,exitlist):
        #读取出口
        global exitLi
        if 1 in exitlist:
            for i in range(len(exitlist)):#一排里面可能有几个1
                if exitlist[i] == 1:
                    exitLi.append([index, i])
    
    #先读取第一行
    temp = list(map(int,input().split(',')))
    readexit(0,temp)
    li.append(temp)
    n = len(temp)
    #新建一个矩阵
    second = [[0 for i in range(n)] for j in range(n)]
    for i in range(1, len(temp)):
        temp = list(map(int,input().split(',')))
        readexit(i,temp)
        li.append(temp)
    #深度遍历每个起点
    def recur(row,column,step):
        if step >= k:
            #大于三就返回
            return 
        if 0 <= column+1 <=n-1:
            if (li[row][column+1] != -1) and (li[row][column+1] != 1):
                #忽略墙和起点
                second[row][column+1] = 1
                recur(row,column+1,step+1)
        if 0 <= column-1 <=n-1:
            if (li[row][column-1] != -1) and (li[row][column-1] != 1):
                #忽略墙和起点
                second[row][column-1] = 1
                recur(row,column-1,step+1)
        if 0 <= row+1 <=n-1:
            if (li[row+1][column] != -1) and (li[row+1][column] != 1):
                #忽略墙和起点
                second[row+1][column] = 1
                recur(row+1,column,step+1)            
        if 0 <= row-1 <=n-1:
            if (li[row-1][column] != -1) and (li[row-1][column] != 1):
                #忽略墙和起点
                second[row-1][column] = 1
                recur(row-1,column,step+1)
    for i in exitLi:
        row = i[0]
        column = i[1]
        recur(row,column,0)
    
    #按照second里面的1进行赋值
    for i in range(n):
        for j in range(n):
            if (li[i][j] == 1) or (li[i][j] == -1):
                li[i][j] = '0'
            elif li[i][j] == 0:
                #两种情况
                if second[i][j] == 1:
                    li[i][j] = '0'
                else:
                    li[i][j] = '1'
    
    for i in range(n):
        print(','.join(li[i]))

通过率为75%。提示超时。这个因为当1与1之间相隔比较近，就会有许多点被重复的递归到，下一章讲一下优化方法，但没有平台让我验证优化后的代码通过率能否达到100%。  
最大的问题是，在每次的深度递归中，不仅会重复遍历点，还会往回遍历点。  
输入为如下，在递归函数里增加语句`print(row,column)`，会发现本章代码有大量重复遍历：  
3  
0,0,0,0,0  
0,0,0,0,0  
0,0,1,0,0  
0,0,0,0,0  
0,0,0,0,0  
虽然大量重复遍历，但输出正确：  
![在这里插入图片描述][70 1]  
second数组元素其实就是代表该元素有没有被遍历过即相当于visited，但这里的代码也不能设置为visited为1即访问过就停止深度遍历，使用如上输入，递归函数修改为如下，即visited为1就不再递归。

def recur(row,column,step):
        print(row,column)
        if step >= k:
            #大于三就返回
            return 
        if 0 <= column+1 <=n-1:
            if (li[row][column+1] != -1) and (li[row][column+1] != 1):
                if second[row][column+1] == 0:
                    #忽略墙和起点
                    second[row][column+1] = 1
                    recur(row,column+1,step+1)
        if 0 <= column-1 <=n-1:
            if (li[row][column-1] != -1) and (li[row][column-1] != 1):
                if second[row][column-1] == 0:
                    #忽略墙和起点
                    second[row][column-1] = 1
                    recur(row,column-1,step+1)
        if 0 <= row+1 <=n-1:
            if (li[row+1][column] != -1) and (li[row+1][column] != 1):
                if second[row+1][column] == 0:
                    #忽略墙和起点
                    second[row+1][column] = 1
                    recur(row+1,column,step+1)            
        if 0 <= row-1 <=n-1:
            if (li[row-1][column] != -1) and (li[row-1][column] != 1):
                if second[row-1][column] == 0:            
                    #忽略墙和起点
                    second[row-1][column] = 1
                    recur(row-1,column,step+1)

运行结果如下，为错误输出：  
![在这里插入图片描述][70 2]  
错误输出的原因如下：  
![在这里插入图片描述][70 3]  
在某一时刻，递归往右走完，红色为已经遍历过的点，由于设置了visited，这些点不能再被遍历到了。  
![在这里插入图片描述][70 4]  
之后递归再向左遍历，蓝色代表能达到的范围，但绿色矩阵本来也应该可以到达，但由于有个红色挡住了，所以绿色区域就不能被遍历到了，所以就造成了错误输出。

# 优化深度递归次数 #

还是建立一个同样的大小的二维数组second，但另每个元素初值为-1，定义second每个元素的含义为传播能力，比如起点的传播能力为k，那么起点对应到second的那个元素的值就设为k；从起点递归到了下一个点A，那么A对应到second的那个元素的值就设为k-1,，以此类推，递归终点的点就会被设置为0。  
在递归函数recur中，k-step-1即k-(step+1)为当前递归的传播能力，second对应元素的值为已经记录的传播能力：  
如果当前递归的传播能力>已经记录的传播能力，那么继续递归，更新传播能力。  
如果当前递归的传播能力<=已经记录的传播能力，那么停止递归。  
![在这里插入图片描述][70 5]  
如上图所示，假设有一个点1即出口的深度遍历是这样，红色数字表示了每个点的传播能力。  
![在这里插入图片描述][70 6]  
现在有另一个出口，它的传播能力是蓝色字体，当它传播到了虚线矩形区域时，当前传播能力就不大于已记录能力了，此时就应该停止深度遍历。这样就减小了递归次数。

**优化的地方在于：最起码递归不会往回走了，传播能力小的也不会继续递归了，但还是会有一定的重复的遍历。**

k  = eval(input())
    li = []#原数组
    exitLi = []#记录出口
    
    def readexit(index,exitlist):
        #读取出口
        global exitLi
        if 1 in exitlist:
            for i in range(len(exitlist)):#一排里面可能有几个1
                if exitlist[i] == 1:
                    exitLi.append([index, i])
    
    #先读取第一行
    temp = list(map(int,input().split(',')))
    readexit(0,temp)
    li.append(temp)
    n = len(temp)
    #新建第二个矩阵
    second = [[-1 for i in range(n)] for j in range(n)]
    for i in range(1, len(temp)):
        temp = list(map(int,input().split(',')))
        readexit(i,temp)
        li.append(temp)
    #深度遍历每个起点
    def recur(row,column,step):
        if step >= k:
            #大于三就返回
            return 
        if 0 <= column+1 <=n-1:
            if (li[row][column+1] != -1) and (li[row][column+1] != 1):
                #忽略墙和起点
                if (k-step-1) > second[row][column+1]:
                    #如果当前传播能力大于已有传播能力，才进行递归
                    second[row][column+1] = k-step-1
                    recur(row,column+1,step+1)
        if 0 <= column-1 <=n-1:
            if (li[row][column-1] != -1) and (li[row][column-1] != 1):
                #忽略墙和起点
                if (k-step-1) > second[row][column-1]:
                    second[row][column-1] = k-step-1
                    recur(row,column-1,step+1)
        if 0 <= row+1 <=n-1:
            if (li[row+1][column] != -1) and (li[row+1][column] != 1):
                #忽略墙和起点
                if (k-step-1) > second[row+1][column]:
                    second[row+1][column] = k-step-1
                    recur(row+1,column,step+1)            
        if 0 <= row-1 <=n-1:
            if (li[row-1][column] != -1) and (li[row-1][column] != 1):
                #忽略墙和起点
                if (k-step-1) > second[row-1][column]:
                    second[row-1][column] = k-step-1
                    recur(row-1,column,step+1)
    for i in exitLi:
        row = i[0]
        column = i[1]
        second[row][column] = 3
        #手动设置起点的传播能力
        recur(row,column,0)
    
    #按照second里面的1进行赋值
    for i in range(n):
        for j in range(n):
            if (li[i][j] == 1) or (li[i][j] == -1):
                li[i][j] = '0'
            elif li[i][j] == 0:
                #两种情况
                if second[i][j] >= 0:
                    li[i][j] = '0'
                else:
                    li[i][j] = '1'
    
    for i in range(n):
        print(','.join(li[i]))

# 宽度遍历 #

使用宽度遍历也是可以的，大概思想也是一样的，每个起点的宽度遍历也是独立的，即每次宽度遍历开始前都要把visited清零的。

#include <bits/stdc++.h>
    #define LL long long
    using namespace std;
    
    const int maxn = 1e3 + 5;
    
    int mat[maxn][maxn], dp[maxn][maxn];
    int vis[maxn][maxn];
    
    int main()
    { 
    	int k;
    	cin >> k;
    	string str;
    	int row = 0;
    	while (cin >> str) { 
    		int num = 0, cnt = 0;//num当前记录的数字，cnt为列
    		for (int j = 0; j < str.size(); j++) { 
    			if (str[j] == ',') { 
    				mat[row][cnt++] = num;//执行这句后再++
    				num = 0;
    			}
    			else if (str[j] == '-') num = -2;//-2加1就为-1
    			else num += str[j] - '0';
    		}
    		mat[row][cnt++] = num;//这句不用++了
    		row++;//行++
    	}
    
    	int sumOut = 0, x[maxn], y[maxn];
    	//记录出口在哪儿
    	for (int i = 0; i < row; i++) { 
    		for (int j = 0; j < row; j++) { 
    			//cout << mat[i][j] << ' ';
    			if (mat[i][j] == 1) { 
    				x[sumOut] = i;
    				y[sumOut++] = j;
    			}
    		}
    		//cout << endl;
    	}
    
    	for (int i = 0; i < maxn; i++) { 
    		for (int j = 0; j < maxn; j++) { 
    			dp[i][j] = maxn;
    			//dp二维数组每个元素都为1005
    		}
    	}
    	int count = 0;//记录队列真正处理了元素的次数
    	//四个方向
    	int direct[4][2] = {  { 1, 0}, { -1, 0}, { 0, 1}, { 0, -1} };
    	for (int i = 0; i < sumOut; i++) { 
    		//每次for循环是一次广度遍历
    		dp[x[i]][y[i]] = 0;//把出口对应元素设置为0，元素代表与起点的距离
    		memset(vis, 0, sizeof(vis));//重新分配visit数组，即每个广度遍历是独立的
    		queue<int> Q;
    		Q.push(x[i] * maxn + y[i]);//入队二维元素的一维序号
    		while (!Q.empty()) { 
    			int pos = Q.front();
    			Q.pop();
    			int posX = pos / maxn, posY = pos % maxn;
    			if (vis[posX][posY]) continue;
    			vis[posX][posY] = 1;
    			for (int j = 0; j < 4; j++) { 
    				int newX = posX + direct[j][0];
    				int newY = posY + direct[j][1];
    				cout << newX << " "<< newY<<endl;
    				if (newX >= 0 && newX < row && newY >= 0 && newY < row && mat[newX][newY] != -1) { 
    					dp[newX][newY] = min(dp[newX][newY], dp[posX][posY] + 1);
    					//更新与起点距离，一种是从1005更新，一种是从已记录更新
    					if (!vis[newX][newY]) Q.push(newX * maxn + newY);
    					//如果访问过，就不会继续宽度遍历
    				}
    			}
    			
    			for (int tempi = 0; tempi < row; tempi++) { 
    				for (int tempj = 0; tempj < row; tempj++) { 
    					if (tempj != row - 1)
    						cout << dp[tempi][tempj] << " ";
    					else
    						cout << dp[tempi][tempj];
    				}
    				cout << endl;
    			}
    			for (int tempi = 0; tempi < row; tempi++) { 
    				for (int tempj = 0; tempj < row; tempj++) { 
    					if (tempj != row - 1)
    						cout << vis[tempi][tempj] << " ";
    					else
    						cout << vis[tempi][tempj];
    				}
    				cout << endl;
    			}
    			count++;
    			cout << endl;
    		}
    	}
    	for (int i = 0; i < row; i++) { //你只需要留下这个for循环里面的输出，其他都是为了调试
    		for (int j = 0; j < row; j++) { 
    			if (mat[i][j] == -1) cout << 0;
    			else if (dp[i][j] <= k) cout << 0;
    			else cout << 1;
    			if (j != row - 1) cout << '\t';
    		}
    		cout << endl;
    	}
    	cout << "count" << count;
    	return 0;
    }
    /* 3 0,0,0,0,0 0,0,0,0,0 0,0,1,0,0 0,0,0,0,0 0,0,0,0,0 */

重点分析宽度遍历的那个while循环：  
1.每执行一次while循环，就置vis\[posX\]\[posY\]为1，并对\[posX\]\[posY\]的四个方向上的点进行处理。

2.处理首先是`dp[newX][newY] = min(dp[newX][newY], dp[posX][posY] + 1)`，dp数组元素代表与起点距离，这句是用于更新与起点距离，一种可能是从初始值1005更新为当前与起点距离，另一种可能是从已记录与起点距离更新为更小的与起点距离。

3.处理然后是`if (!vis[newX][newY]) Q.push(newX * maxn + newY)`，将四个方向的点中没有被访问的点加入队列，以待之后进行访问。

4.有可能会把一个未被访问过的点多次加入到队列当中，如果说C++提供的队列能够有功能检测元素是否在队列中，那就好办了，直接改成`if (!vis[newX][newY] & 不在队列中) Q.push(newX * maxn + newY)`，但并没有这个功能，所以一个点重复加入队列中是无法避免的事，但可以在while循环前部分加入`if (vis[posX][posY]) continue`，以免程序进行重复的操作。

下面的示意图将演示“一个点重复加入队列中”：  
![在这里插入图片描述][70 7]  
第一次出队后，周围四个方向的点就入队，之后的操作，就是再分别依次地对这四个点进行出队操作。  
![在这里插入图片描述][70 8]  
假设之后再对2,3这个点进行出队操作，又会将上图中红圈里的点入队，注意黄色数字0将会被重复入队。  
![在这里插入图片描述][70 9]  
假设之后再对3,2这个点进行出队操作，又会将上图中红圈里的点入队，这时黄色数字0被重复入队。  
![在这里插入图片描述][70 10]  
可以想象，在将最初入队的四个点都出队后，上图的四个黄色的点都会被重复入队。

# 宽度遍历优化 #

也是使用传播能力的思想，只是宽度遍历中变成了与起点距离，与起点距离就是反过来想。每次宽度遍历都不会所有点遍历一遍了。

for (int i = 0; i < sumOut; i++) { 
    		//每次for循环是一次广度遍历
    		dp[x[i]][y[i]] = 0;//把出口对应元素设置为0，元素代表与起点的距离
    		memset(vis, 0, sizeof(vis));//重新分配visit数组，即每个广度遍历是独立的
    		queue<int> Q;
    		Q.push(x[i] * maxn + y[i]);//入队二维元素的一维序号
    		while (!Q.empty()) { 
    			int pos = Q.front();
    			Q.pop();
    			int posX = pos / maxn, posY = pos % maxn;
    			if (vis[posX][posY]) continue;
    			if (!vis[posX][posY] & (dp[posX][posY] == k)) { 
    				//如果在当前遍历中还没有访问过，且距离为k即最远了，就只更新visited
    				vis[posX][posY] = 1;
    				continue;
    			} 
    			vis[posX][posY] = 1;
    			for (int j = 0; j < 4; j++) { 
    				int newX = posX + direct[j][0];
    				int newY = posY + direct[j][1];
    				cout << newX << " "<< newY<<endl;
    				if (newX >= 0 && newX < row && newY >= 0 && newY < row && mat[newX][newY] != -1 && mat[newX][newY] != 1) { 
    				//加了避开其他起点
    					
    					if (!vis[newX][newY] & ((dp[posX][posY] + 1)< dp[newX][newY])) Q.push(newX * maxn + newY);
    					//只有传播能力更强才能入队
    					//如果访问过，就不会继续宽度遍历
    					dp[newX][newY] = min(dp[newX][newY], dp[posX][posY] + 1);
    					
    				}
    			}
    			
    			for (int tempi = 0; tempi < row; tempi++) { 
    				for (int tempj = 0; tempj < row; tempj++) { 
    					if (tempj != row - 1)
    						cout << dp[tempi][tempj] << " ";
    					else
    						cout << dp[tempi][tempj];
    				}
    				cout << endl;
    			}
    			for (int tempi = 0; tempi < row; tempi++) { 
    				for (int tempj = 0; tempj < row; tempj++) { 
    					if (tempj != row - 1)
    						cout << vis[tempi][tempj] << " ";
    					else
    						cout << vis[tempi][tempj];
    				}
    				cout << endl;
    			}
    			count++;
    			cout << endl;
    		}
    	}

[70]: /images/20220508/4a9f4cfc9a1f4257a05070c14abf606c.png
[70 1]: /images/20220508/2e075139e59a4a8da7f8f6d2cb2616df.png
[70 2]: /images/20220508/dcebeb454a9743b48458d9cc85e9af7e.png
[70 3]: /images/20220508/387a390d5ad64779902cf81e2b1a8d3b.png
[70 4]: /images/20220508/744569b5c8d840c6b843c11afda3c886.png
[70 5]: /images/20220508/920b3066561b480997cf92b5517957fd.png
[70 6]: /images/20220508/852cf92141404c18a26391bd860632f4.png
[70 7]: /images/20220508/76c8894b229b4bc095ff8dedcc368467.png
[70 8]: /images/20220508/4246f515712d41c886a37233626d48a6.png
[70 9]: /images/20220508/667670df4eb9417cba16f759f7beb328.png
[70 10]: /images/20220508/4d8d8e3dfdd4472d94aa2215cf30fa73.png