#include<iostream> #include<queue> #include<string> #include<cstdio> using namespace std; struct Route{ int x; int y; int step; char pos; }; queue<Route>myqueue; int main(){ int n,m; cin>>n>>m; char a[105][105]; char s; bool isvis[105][105]; for(int i=0;i<105;i++){ for(int j=0;j<105;j++){ isvis[i][j]=false; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>s; a[i][j]=s; } } Route first; first.x=1; first.y=1; first.pos=a[first.x][first.y]; first.step=0; myqueue.push(first); isvis[first.x][first.y]=true; while(!myqueue.empty()){ Route cur=myqueue.front(); myqueue.pop(); if(cur.pos=='E'){ cout<<cur.step<<endl;break; } else{ if(isvis[cur.x+1][cur.y]==false && cur.x+1<=n && a[cur.x+1][cur.y]!='#'){ Route neighbor; neighbor.x=cur.x+1; neighbor.y=cur.y; neighbor.step=cur.step+1; neighbor.pos=a[neighbor.x][neighbor.y]; isvis[neighbor.x][neighbor.y]=true; myqueue.push(neighbor); } if(isvis[cur.x][cur.y+1]==false && cur.y+1<=m && a[cur.x][cur.y+1]!='#'){ Route neighbor; neighbor.x=cur.x; neighbor.y=cur.y+1; neighbor.step=cur.step+1; neighbor.pos=a[neighbor.x][neighbor.y]; isvis[neighbor.x][neighbor.y]=true; myqueue.push(neighbor); } if(isvis[cur.x-1][cur.y]==false && cur.y-1>=1 && a[cur.x-1][cur.y]!='#'){ Route neighbor; neighbor.x=cur.x-1; neighbor.y=cur.y; neighbor.step=cur.step+1; neighbor.pos=a[neighbor.x][neighbor.y]; isvis[neighbor.x][neighbor.y]=true; myqueue.push(neighbor); } if(isvis[cur.x][cur.y-1]==false && cur.y-1>=1 && a[cur.x][cur.y-1]!='#'){ Route neighbor; neighbor.x=cur.x; neighbor.y=cur.y-1; neighbor.step=cur.step+1; neighbor.pos=a[neighbor.x][neighbor.y]; isvis[neighbor.x][neighbor.y]=true; myqueue.push(neighbor); } } } } |
Double click to view unformatted code.