题意:从*点开始,标记所有能走到的点,X代表墙,下划线原样输出
AC：40ms
#include<stdio.h>
#include<iostream>
#include<queue>
#include<memory.h>
using namespace std;
struct DIR
{
int r;
int c;
} dir[] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
const int MAXR = 31;
const int MAXC = 81;
void bfs(queue<DIR> q, int maps[][MAXC])
{
DIR d;
while (!q.empty())
{
d = q.front();
q.pop();
int nr, nc;
for(int i = 0; i < 4; i++)
{
nr = d.r + dir[i].r;
nc = d.c + dir[i].c;
if(maps[nr][nc] != 1)
continue;
maps[nr][nc] = 2;
DIR dd;
dd.r = nr;
dd.c = nc;
q.push(dd);
}
} }
int main()
{
freopen("d:\\1.txt", "r", stdin);
int n;
cin >> n;
getchar();
while (n--)
{
int r = 0, c = 0;
char cc;
int maps[MAXR][MAXC];
int sr, sc;
memset(maps, 0, sizeof(maps));
string str;
//getline(cin, str);
while (getline(cin, str))
{
if(str.at(0) == '_')
break;
int length = str.length();
if(length > c)
c = length;
for(int i = 0; i < length; i++)
{
cc = str.at(i);
if(cc == ' ' || cc == '*')
{
maps[r][i] = 1;
}
if(cc == '*')
{
sr = r;
sc = i;
}
if(cc == 'X')
{
maps[r][i] = -1;
}
}
r++;
}
DIR d;
d.r = sr;
d.c = sc;
queue<DIR> q;
q.push(d);
bfs(q, maps);
for(int i = 0; i < r; i++)
{
for(int j = 0; j < c; j++)
{
if(maps[i][j] == 0)
break;
if(maps[i][j] == -1)
cout << 'X';
if(maps[i][j] == 2)
cout << '#';
if(maps[i][j] == 1)
cout << ' ';
}
cout << endl;
}
cout << str << endl;
}
return 0;
}