Niuke winter vacation training 6 maze 2

G

The question ：
To give you one n*m The map of , Each point has a direction , It means which direction you can go at the current point without spending energy . Now? , Let you find out the minimum number of modifications , So that the calf can learn from 11 Go to the nm. At the same time, output the modified scheme , It's about which direction to change at that point .

reflection ：
At that time, I saw this question , How to change it , No idea , But I did that problem a few days ago Cattle go through the maze It feels a little like , That question is the smallest dictionary order for you to find the way out , Then I'll let dx and dy The sequence of array traversal is to start from the smallest dictionary order , Finally, just output the answer . But this question , Let me revise , It feels very difficult .
This problem uses a double ended queue , Greedy type of search , A point can be traversed many times , As long as he can come from a smaller place . Generally, it is also with distra equally , Add... To it if(vis[x][y]) coninue ; vis[x][y] = 1; However, the structure of general topics will make this entry limit perfect , If it's not perfect , You can add one by yourself cnt Quit when you feel almost done . That is, if you need to change direction , Then put it in back, Or put it in front. Such purpose is to update greedily , Try not to use magic .

Code ：

 The code of this question ：

int T,n,m,k;
char va[M][M];
int dx[4] = {
    0,0,-1,1};
int dy[4] = {
    -1,1,0,0};
char dir[4] = {
    'L','R','U','D'};
int dist[M][M],vis[M][M];
PII pre[M][M];

void bfs()
{
    
	for(int i=1;i<=n;i++)
	{
    
		for(int j=1;j<=m;j++)
		{
    
			vis[i][j] = 0;
			dist[i][j] = inf;
		}
	}
	deque<PII > q;
	q.push_back({
    1,1});
	dist[1][1] = 0;
	while(q.size())
	{
    
		auto now = q.front();
		q.pop_front();
		int x = now.fi,y = now.se;
		if(vis[x][y]) continue;
		vis[x][y] = 1;
		for(int i=0;i<4;i++)
		{
    
			int dis = dist[x][y]+(dir[i]!=va[x][y]);
			int xx = x+dx[i],yy = y+dy[i];
			if(xx<1||xx>n||yy<1||yy>m) continue;
			if(dist[xx][yy]>dis)
			{
    
				pre[xx][yy] = {
    x,y};
				dist[xx][yy] = dis;
				if(dist[xx][yy]==dist[x][y]) q.push_front({
    xx,yy});
				else q.push_back({
    xx,yy});
			}
		}
	}
}

signed main()
{
    
	IOS;
	cin>>T;
	while(T--)
	{
    
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
    
			for(int j=1;j<=m;j++)
			cin>>va[i][j];
		}
		bfs();
		cout<<dist[n][m]<<"\n";
		int x = n,y = m;
		while(pre[x][y].fi!=0||pre[x][y].se!=0)
		{
    
			int xx = pre[x][y].fi,yy = pre[x][y].se;
			char op;
			if(xx+1==x) op = 'D';
			if(xx-1==x) op = 'U';
			if(yy+1==y) op = 'R';
			if(yy-1==y) op = 'L';
			if(va[xx][yy]!=op) cout<<xx<<" "<<yy<<" "<<op<<"\n";
			x = xx,y = yy;
		}
	}
	return 0;
}

 Niuniu maze code ：

int T,n,m,k;
char va[M][M];
int vis[M][M];
int dist[M][M];
PII ne[M][M];

int dx[4] = {
    1,0,0,-1};
int dy[4] = {
    0,1,-1,0};

bool bfs()
{
    
	queue<PII > q;
	q.push({
    1,1});
	vis[1][1] = 1;
	while(q.size())
	{
    
		auto now = q.front();
		q.pop();
		int x = now.fi,y = now.se;
		if(x==n&&y==m) return true;
		for(int i=0;i<4;i++)
		{
    
			int xx = x+dx[i],yy = y+dy[i];
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]&&va[xx][yy]=='0')
			{
    
				vis[xx][yy] = 1;
				dist[xx][yy] = dist[x][y]+1;
				ne[xx][yy] = {
    x,y};
				q.push({
    xx,yy});
			}
		}
	}
	return false;
}

signed main()
{
    
	IOS;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
    
		for(int j=1;j<=m;j++)
		cin>>va[i][j];
	}
	if(!bfs()) cout<<-1;
	else
	{
    
		int x = n,y = m;
		vector<char > anw;
		while(ne[x][y].fi!=0&&ne[x][y].se!=0)
		{
    
			int xx = ne[x][y].fi,yy = ne[x][y].se;
			if(xx+1==x) anw.pb('D');
			if(xx-1==x) anw.pb('U');
			if(yy+1==y) anw.pb('R');
			if(yy-1==y) anw.pb('L');
			x = xx,y = yy;
		}
		reverse(anw.begin(),anw.end());
		cout<<anw.size()<<"\n";
		for(auto t:anw) cout<<t;
	}
	return 0;
}

summary ：
Gain more experience , Come on .