灯塔问题

灯塔问题"/>

灯塔问题

题目名称：灯塔问题

题目链接：灯塔问题

描述

给定一个NxM的方格矩阵，其中某些方格中包含有一座灯塔。

已知灯塔可以照射到上下左右与它在同一排或同一列的方格，除非被矩阵边缘或者另一座灯塔阻挡。

请你计算矩阵中每一个不包含灯塔的方格，同时被多少座灯塔照射到？

输入

第一行包含2个整数N和M。

以下N行每行包含M个字符，代表方格矩阵。其中字符B代表灯塔，O代表空方格。

对于80%的数据，1 <= N, M <= 100

对于100%的数据，1 <= N, M <= 1000

输出

一个NxM的字符矩阵。

将输入的矩阵中的每一个字符O替换为一个0~4的数字，代表该方格同时被多少座灯塔照射到。B字符保持不变

样例输入

4 4
OOOO
BOBO
OOOO
OBBO

样例输出

1110
B3B1
1120
2BB1

解题思路

利用maps数组标记灯塔位置，利用table表示每个位置可以被灯塔照射的个数，利用深度优先搜索算法对寻找每个灯塔可以照射的范围即可

完整代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 1010
int table[N][N];
char maps[N][N];
int n,m;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};void dfs(int row,int col,int dir)
{while(maps[row][col]!='B'){table[row][col]++;row=row+dx[dir];col=col+dy[dir];}
}int main()
{
//	freopen("in.txt", "r", stdin);memset(table,0,sizeof(table));cin>>n>>m;cin.ignore();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>maps[i][j];}cin.ignore(); }for(int i=0;i<=n;i++){maps[i][0]='B';maps[i][m+1]='B';}for(int i=0;i<=m;i++){maps[0][i]='B';maps[n+1][i]='B';}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(maps[i][j]=='B'){for(int dir=0;dir<4;dir++){dfs(i+dx[dir],j+dy[dir],dir);}}}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(maps[i][j]=='B'){cout<<'B';}else{cout<<table[i][j];}}cout<<endl;}return 0;
}