[ABC295B] Bombs 题解

发布时间 2023-03-28 18:20:17作者: mark0575

题目大意:

给出一张地图,其中 # 表示障碍物,如果某个位置上有数字,就表示这个位置上有一个范围为这个数字的炸弹。在这个炸弹范围内的所有格子都要变为 .。问我们最后的地图是怎样的。

解题思路:

因为这里的距离是曼哈顿距离,所以我们可以以一个炸弹为中心,在这个距离内跑一遍深搜,把遍历到的格子改成 .。但是,如果把一个没有操作过的格子变成 .,会影响最后的结果。因此,我们可以用两个数组去存储这张地图。

code:

#include<bits/stdc++.h>
using namespace std;
int n,m;
char c[1001][1001];//地图
char b[1001][1001];
int dx[101]={1,0,-1,0};//方向
int dy[101]={0,1,0,-1};
void dfs(int x,int y,int s,int os)//遍历,os为最长长度
{
	b[x][y]='.';
	if(s==os)
	{
		return ;
	}
	for(int i=0;i<4;i++)
	{
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx<=n&&yy<=m&&yy>=1&&xx>=1)
		{
			b[xx][yy]='.';//修改
			dfs(xx,yy,s+1,os);
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>c[i][j];
			b[i][j]=c[i][j];//存到另一张表上
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(c[i][j]<='9'&&c[i][j]>='0')//是否是炸弹
			{
				dfs(i,j,0,c[i][j]-'0');
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cout<<b[i][j];
		}
		cout<<"\n";
	}
	return 0;
}