解题思路:
做笔记专用
注意事项:
做笔记专用,不喜勿喷
参考代码:
#include<iostream> #include<string.h> #include<queue> #include<stdio.h> using namespace std; int n,m; char mp[501][501]; int book[501][501]; int rode[4][2]={1,0,0,-1,0,1,-1,0}; struct node { int x,y,step,dir[10000]; }; void bfs() { queue<node> q; node now,next; now.x=0;now.y=0; now.step=0;now.dir[0]=-1; q.push(now); while(!q.empty()) { now=q.front(); q.pop(); if(now.x==n-1&&now.y==m-1) { cout<<now.step<<endl; for(int i=1;i<=now.step;i++) { if(now.dir[i]==0) cout<<"D"; else if(now.dir[i]==1) cout<<"L"; else if(now.dir[i]==2) cout<<"R"; else if(now.dir[i]==3) cout<<"U"; } return ; } for(int i=0;i<4;i++) { int tx=now.x+rode[i][0]; int ty=now.y+rode[i][1]; if(tx>=0&&tx<n&&ty>=0&&ty<m&&book[tx][ty]==0&&mp[tx][ty]=='0') { book[tx][ty]=1; next=now; next.x=tx; next.y=ty; next.step=now.step+1; next.dir[next.step]=i; q.push(next); } } } } int main() { cin>>n>>m; for(int i=0;i<n;i++) { scanf("%s",mp[i]); } memset(book,0,sizeof(book)); bfs(); return 0; }
0.0分
1 人评分