【算法练习 | C】引爆炸弹——深度搜索算法

桃扇骨 2022-12-04 07:52 92阅读 0赞

在一个 n×m 的方格地图上，某些方格上放置着炸弹。手动引爆一个炸弹以后，炸弹会把炸弹所在的行和列上的所有炸弹引爆，被引爆的炸弹又能引爆其他炸弹，这样连锁下去。

现在为了引爆地图上的所有炸弹，需要手动引爆其中一些炸弹，为了把危险程度降到最低，请算出最少手动引爆多少个炸弹可以把地图上的所有炸弹引爆。

**输入格式**  
第一行输两个整数 n,m，用空格隔开。

接下来 n 行，每行输入一个长度为 m 的字符串，表示地图信息。0表示没有炸弹，1表示炸弹。

**数据约定**

对于 60% 的数据：1≤n,m≤100；

对于 100% 的数据：1≤n,m≤1000；

数据量比较大，不建议用cin输入。

**输出格式**  
输出一个整数，表示最少需要手动引爆的炸弹数。

**样例输入**

5 5
    00010
    00010
    01001
    10001
    01000

**样例输出**

下面这种普通解法会超时：

// 超时 
    
    #include <stdio.h>
    
    char map[1001][1001];
    int book[1001][1001] = { 0};
    int book2[1001][2] = { 0};
    int sum,n,m;
    
    void dfs(int x, int y) { 
    	int tx,ty,k,i,j;
    	int next[4][2] = { 	{  0, 1},
    						{  1, 0},
    						{  0,-1},
    						{ -1, 0}};
    	for(k=0;k<4;k++) { 
    		tx = x + next[k][0];
    		ty = y + next[k][1];
    		
    		if( tx<0 || ty<0 || tx>n-1 || ty>m-1) { 
    			continue;
    		}
    		
    		if(book[tx][ty]==0) { 
    			book[tx][ty] = 1;	
    			if(map[tx][ty]!='0') { 
    				if(map[tx][ty]=='1') { 
    					sum++;
    				}
    				map[tx][ty] = '0';
    				for(i=0;i<n;i++) { 
    					if(map[i][ty]=='1') { 
    						map[i][ty]='2';
    					}
    				}
    				for(j=0;j<m;j++) { 
    					if(map[tx][j]=='1') { 
    						map[ty][j]='2';
    					}
    				}
    			}
    			dfs(tx,ty);		
    		}
    	}
    }
    
    
    int main() { 
    	int i,j;
    	scanf("%d %d",&n,&m);
    	for(i=0;i<n;i++) { 
    		scanf("%s",map[i]);
    	}
    	book[0][0] = 1;
    	sum=0;
    	dfs(0,0);
    	printf("%d",sum);
    	
    	return 0;
    }

为解决超时问题，引爆炸弹时对行、列进行标记：

#include <stdio.h>
    #include <time.h>
    
    char map[1001][1001];
    int book[1001][1001];
    int row[1001]={ 0}, col[1001]={ 0};
    int sum,n,m;
    
    void dfs(int x, int y) { 
    	int i;
    	map[x][y] = '0';
    	if(row[x]==0) { 
    		row[x] = 1;
    		for(i=0;i<m;i++) { 
    			if(map[x][i]=='1') { 
    				dfs(x,i);
    			}
    		}
    	}
    	if(col[y]==0) { 
    		col[y] = 1;
    		for(i=0;i<n;i++) { 
    			if(map[i][y]=='1') { 
    				dfs(i,y);
    			}
    		}
    	}
    }
    
    void dfs2(int x, int y) { 
    	int tx,ty,k,i,j;
    	int next[4][2] = { 	{  0, 1},
    						{  1, 0},
    						{  0,-1},
    						{ -1, 0}};
    	for(k=0;k<4;k++) { 
    		tx = x + next[k][0];
    		ty = y + next[k][1];
    		
    		if( tx<0 || ty<0 || tx>n-1 || ty>m-1) { 
    			continue;
    		}
    		
    		if(book[tx][ty]==0) { 
    			book[tx][ty] = 1;
    			if(map[tx][ty]=='1'){ 
    				sum++;
    				dfs(tx, ty);
    			}
    			dfs2(tx, ty);
    		}
    	}
    	return;
    }
    
    
    int main() { 
    	int i,j;
    	scanf("%d %d",&n,&m);
    	for(i=0;i<n;i++) { 
    		scanf("%s",map[i]);
    	}
    	sum=0;
    	book[0][0] = 1;
    	//深度搜索方案
    	dfs2(0,0);
    	
    	/* //普通方案 for(i=0;i<n;i++) for(j=0;j<m;j++) if(map[i][j]=='1'){//对于当前有炸弹时 dfs(i,j); sum++; } */
    	
    	//printf("%d",sum);
    
    	return 0;
    }