首页 > 代码库 > uva-784-水题-搜索
uva-784-水题-搜索
题意:从*点开始,标记所有能走到的点,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-水题-搜索
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。