当前位置:网站首页>Niuke winter vacation training 6 maze 2
Niuke winter vacation training 6 maze 2
2022-07-06 08:44:00 【Lovely and beautiful girl】
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 .
边栏推荐
- Problems in loading and saving pytorch trained models
- MySQL learning record 11jdbcstatement object, SQL injection problem and Preparedstatement object
- 704 二分查找
- How to conduct interface test? What are the precautions? Nanny level interpretation
- [embedded] cortex m4f DSP Library
- Colorlog combined with logging to print colored logs
- egg. JS project deployment online server
- Navicat Premium 创建MySql 创建存储过程
- Charging interface docking tutorial of enterprise and micro service provider platform
- 【Nvidia开发板】常见问题集 (不定时更新)
猜你喜欢
角色动画(Character Animation)的现状与趋势
FairGuard游戏加固:游戏出海热潮下,游戏安全面临新挑战
Detailed explanation of heap sorting
egg. JS getting started navigation: installation, use and learning
Beijing invitation media
Computer cleaning, deleted system files
sublime text没关闭其他运行就使用CTRL+b运行另外的程序问题
C语言双指针——经典题型
Deep analysis of C language data storage in memory
Image,cv2读取图片的numpy数组的转换和尺寸resize变化
随机推荐
Detailed explanation of heap sorting
Deep anatomy of C language -- C language keywords
查看局域网中电脑设备
可变长参数
广州推进儿童友好城市建设,将探索学校周边200米设安全区域
ROS compilation calls the third-party dynamic library (xxx.so)
What is the role of automated testing frameworks? Shanghai professional third-party software testing company Amway
TCP/IP协议
[embedded] print log using JLINK RTT
@JsonBackReference和@JsonManagedReference(解决对象中存在双向引用导致的无限递归)
Revit secondary development Hof method calls transaction
China vanadium battery Market Research and future prospects report (2022 Edition)
gcc动态库fPIC和fpic编译选项差异介绍
Research Report on Market Research and investment strategy of microcrystalline graphite materials in China (2022 Edition)
Colorlog combined with logging to print colored logs
如何进行接口测试测?有哪些注意事项?保姆级解读
egg. JS getting started navigation: installation, use and learning
View computer devices in LAN
ROS编译 调用第三方动态库(xxx.so)
Image,cv2读取图片的numpy数组的转换和尺寸resize变化