01bfs 68pts 边界开大了的求调
查看原帖
01bfs 68pts 边界开大了的求调
484586
vicissitudes楼主2023/10/4 17:24
#include<bits/stdc++.h>
using namespace std;

const int N = 510;
int n, m, ans = INT_MAX;
char mp[N][N];
struct node{
	int x, y, cost;
};
int dx[4] = {-1, 1, -1, 1};
int dy[4] = {-1, -1, 1, 1};
bool vis[N][N];

int calc(int a, int b, int num)
{
	if(num == 0)
	{
		if(mp[a - 1][b - 1] == '/') return 1;
		else return 0;
	}
	if(num == 1)
	{
		if(mp[a][b - 1] == '/') return 0;
		else return 1;
	}
	if(num == 2)
	{
		if(mp[a - 1][b] == '/') return 0;
		else return 1;
	}
	if(num == 3)
	{
		if(mp[a][b] == '/') return 1;
		else return 0;
	}
}

void bfs()
{
	deque<node> q;
	q.push_front({1, 1, 0});
	while(!q.empty())
	{
		auto x = q.front(); q.pop_front();
		for(int i = 0; i < 4; i ++)
		{
			int nx = x.x + dx[i];
			int ny = x.y + dy[i];
			if(nx <= n + 1 && ny <= m + 1 && nx >= 1 && ny >= 1 && !vis[nx][ny])
			{
				vis[nx][ny] = true;
				int mon = calc(x.x, x.y, i);
				if(nx == n + 1 && ny == m + 1) 
				{
					vis[nx][ny] = false;
					ans = min(ans, x.cost + mon);
				}
				else if(mon == 1) q.push_back({nx, ny, x.cost + 1});
				else q.push_front({nx, ny, x.cost});  
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++)
			cin >> mp[i][j];
	
	bfs();
	if(ans == INT_MAX) cout << "NO SOLUTION";
	else cout << ans;
	return 0;
} 
2023/10/4 17:24
加载中...