洛谷 P2298 【Mzc和男家丁的游戏】

这道题还是挺水的，广搜模板题，注意一下细节就是了。

：码代上上代码：

#include <bits/stdc++.h>

using namespace std;

int n , m , sx , sy , ans = -1;

int dx[] = {1 , 0 , -1 , 0} , dy[] = {0 , 1 , 0 , -1};	//方向

bool vis[2010][2010];

char st[2010][2010];

struct node{

	int x , y , s;	//坐标和走到当前点的时间

};

queue<node> q;

void bfs(){

	node now;

	now.x = sx , now.y = sy , now.s = 0;

	q.push(now);

	vis[sx][sy] = 1;

	while(!q.empty()){

		now = q.front();

		if(st[now.x][now.y] == 'd'){	//因为是广搜，所以第一个就是最优解

			ans = now.s;

			break;

		}

		q.pop();

		for(int v = 0; v <= 3; v++){

			node nxt;

			nxt.x = now.x + dx[v] , nxt.y = now.y + dy[v] , nxt.s = now.s + 1;

			if(!vis[nxt.x][nxt.y] && nxt.x <= n && nxt.x >= 1 && nxt.y >= 1 && nxt.y <= m && st[nxt.x][nxt.y] != '#'){

				vis[nxt.x][nxt.y] = 1;

				q.push(nxt);

			}

		}

	}

}

int main(){

	cin >> n >> m;

	for(int i = 1; i <= n; i++)

		for(int j = 1; j <= m; j++){

			cin >> st[i][j];

			if(st[i][j] == 'm') sx = i , sy = j;

		}

	bfs();

	if(ans == -1) cout << "No Way!";

	else cout << ans;

	return 0;

}

巴特西

洛谷 P2298 【Mzc和男家丁的游戏】

最新文章

热门文章

巴特西

洛谷 P2298 【Mzc和男家丁的游戏 】

最新文章

热门文章

洛谷 P2298 【Mzc和男家丁的游戏】