悬关QwQ
查看原帖
悬关QwQ
718017
Dream__maker楼主2024/4/1 22:45
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
char mp[N][N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int n, m, sx, sy, ex, ey, dis[N][N];
struct node {int x, y;};
queue <node> q;
int check(int xx, int yy, int stp)
{
	if(xx < 1 || xx > n || yy < 1 || yy > m) return 0;
	if(mp[xx][yy] == '*') return 0;
	if(stp >= dis[xx][yy]) return 0;
	return 1;
}
void bfs()
{
	while(!q.empty())
	{
		node u = q.front();
		q.pop();
		for(int i = 0; i < 4; i++)
		{
			int xx = u.x + dx[i], yy = u.y + dy[i];
			while(check(xx, yy, dis[u.x][u.y] + 1))
			{
				dis[xx][yy] = dis[u.x][u.y] + 1;
				q.push({xx, yy});
				xx += dx[i], yy += dy[i];
			}
		}
	}
}
int main()
{
	//int dat = 2139062143;
	memset(dis, 0x7f, sizeof(dis));
	cin >> m >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> mp[i] + 1;
		for(int j = 1; j <= m; j++)
		{
			if(mp[i][j] == 'C') 
			{
				if(sx) ex = i, ey = j;
				else sx = i, sy = j;
			}
		}
	}
	dis[sx][sy] = -1;
	q.push({sx, sy});
	bfs();
//	for(int i = 1; i <= n; i++)
//	{
//		for(int j = 1; j <= m; j++)
//		{
//			cout << dis[i][j] << ' ';
//		}
//		cout << endl;
//	}
	cout << dis[ex][ey] << endl;
	return 0;
}
2024/4/1 22:45
加载中...