如何优化
查看原帖
如何优化
1031733
xigou1834楼主2023/10/2 09:35
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<char>>a;//char a[130][130];
vector<vector<bool>>vis;//bool vis[130][130];
vector<vector<bool>>vis1;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};
const int vx[] = {0, 0, -1, 1, -1, 1, -1, 1};
const int vy[] = {-1, 1, 0, 0, -1, 1, 1, -1};
int hx, hy, jx, jy;
void reset_vis1()
{
	vis1.resize(n + 1, vector<bool>(m + 1, false));
	for(int i = 0;i <= n;i ++)
	{
		for(int j = 0;j <= m;j ++)
		{
			vis1[i][j] = false;
		}
	}
}
void bfs()
{
	if(vis[hx][hy] == true) 
	{
		cout << 0 << endl;
		return ;
	}
	int q[16905][5] = {0}, h = 1, t = 1;
	//bool vis1[130][130] = {false};
	reset_vis1();
	q[1][1] = hx;
	q[1][2] = hy;
	q[1][3] = 0;
	q[1][4] = 0;
	while(h <= t)
	{
		for(int i = 0;i < 4;i ++)
		{
			int nx = q[h][1] + dx[i];
			int ny = q[h][2] + dy[i];
			if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && !vis1[nx][ny] && a[nx][ny] != 'X')
			{
				vis1[nx][ny] = true;
				t ++;
				q[t][1] = nx;
				q[t][2] = ny;
				q[t][3] = h;
				q[t][4] = q[h][4] + 1;
				if(vis[nx][ny] == true)
				{
					cout << q[t][4] << endl;
					return ;
				}
			}
		}
		h ++;
	}
	cout << "Poor Harry\n";
	return ;
}
void reset_vis()
{
	vis.resize(n + 1, vector<bool>(m + 1, false));
	for(int i = 0;i <= n;i ++)
	{
		for(int j = 0;j <= m;j ++)
		{
			vis[i][j] = false;
		}
	}
}
void reset_a()
{
	a.resize(n + 1, vector<char>(m + 1, ' '));
	for(int i = 0;i <= n;i ++)
	{
		for(int j = 0;j <= m;j ++)
		{
			a[i][j] = ' ';
		}
	}
}
int main()
{
	cin >> n >> m;
	reset_a();
	for(int i = 1;i <= n;i ++)
	{
		for(int j = 1;j <= m;j ++)
		{	
			cin >> a[i][j];
		}
	}
	while (true)
	{
		cin >> jx >> jy >> hx >> hy;
		if(jx == 0 && jy == 0 && hx == 0 && hy == 0) return 0;
		reset_vis();//memset(vis, false, sizeof(vis));
		for(int i = 0;i < 8;i ++)
		{
			int nx = jx, ny = jy;
			while(nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] != 'X')
			{
				vis[nx][ny] = true;
				nx += vx[i], ny += vy[i];
			}
		}
		bfs();
	}
}

2023/10/2 09:35
加载中...