brush txt ons queue out bre ont tin
题意: 从 * 点开始, 标记所有能走到的点, 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;
- }
uva-784 - 水题 - 搜索
来源: http://www.bubuko.com/infodetail-2094868.html