首页 > 代码库 > 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-水题-搜索