Red and Black

<题目链接>

代码(BFS)

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
void BFS(int x, int y);

int step;
int n, m;
int start_x, start_y;
char mp[30][30];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0}; // 右、下、左、上,4个方向的 搜索 

struct node 
{ 
	int x, y; 
};

int main()
{
	while(cin>>n>>m && (n||m))
	{
		step = 0;
		for (int i=0; i<m; i++)
		{
			for (int j=0; j<n; j++)
			{
				cin>>mp[i][j];
				if (mp[i][j] == '@')
				{
					start_x = i;
					start_y = j;
				}
			}
		}
		BFS(start_x, start_y);
	}	
	return 0;
} 

void BFS(int x, int y)
{
	queue <node> q;
	node start, next; // 当前的点的坐标、下一步的点的坐标 
	start.x = x;
	start.y = y;
	q.push(start);
	mp[start.x][start.y] = '#'; // 压入队列的同时,标记此点已经走过,不可以继续走 
	while (!q.empty())
	{
		start.x = q.front().x;
		start.y = q.front().y;
		q.pop(); 
		step++; // 出队的同时,步数 +1 
		for (int i=0; i<4; i++)
		{
			next.x = start.x + dx[i];
			next.y = start.y + dy[i];
			if(next.x >= 0 && next.x < m && next.y >= 0 && next.y < n && mp[next.x][next.y] == '.')
			{
				q.push(next);
				mp[next.x][next.y] = '#';
			}
		}
	}
	cout<<step<<endl;
}

代码(DFS)

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
void DFS(int x, int y);

int step;
int n, m;
char mp[30][30];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0}; // 右、下、左、上,4个方向的 搜索 

int main()
{
	int start_x, start_y;
	while(cin>>n>>m && (m||n)) 
	{
		step = 0;
		for (int i=0; i<m; i++) // 输入地图
		{
			for (int j=0; j<n; j++)
			{
				cin>>mp[i][j]; 
				if (mp[i][j] == '@') // 寻找起点 
				{
					mp[i][j]='#'; 
					start_x = i;
					start_y = j;
				}
			}
		} 
		DFS(start_x, start_y); // 开始搜索
		cout<<step<<endl;
	}
	return 0;
}

void DFS(int x, int y)
{
	mp[x][y] = '#'; // 标记当前 x y 已经走过	
	step++; // 步数 +1 
	for (int i=0; i<4; i++) // 4个方向的 搜索 
	{
		int next_x = x + dx[i];
		int next_y = y + dy[i];  
		if (next_x >= 0 && next_x < m && next_y >= 0 && next_y < n && mp[next_x][next_y] == '.')  // 判断当前位置的下一步
		{			
			DFS(next_x, next_y); // 下一步 未越界,且可以走时,进入下一层函数中搜索 
		}
	} 
} 

上一篇:设计模式-责任链模式


下一篇:初步使用markdown