灯塔问题"/>
灯塔问题
题目名称:灯塔问题
题目链接:灯塔问题
描述
给定一个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;
}
更多推荐
灯塔问题
发布评论