首页 > 代码库 > poj1753--模拟
poj1753--模拟
/** \brief poj 1573 * * \param date 2014/8/5 * \param state * \return memory 744k time 0ms * */ #include <iostream> #include <fstream> #include <cstring> #include <queue> using namespace std; const int MAXN=11; int Map[MAXN][MAXN]; //int vis[MAXN][MAXN]; int DirX[4]={0,1,0,-1}; int DirY[4]={1,0,-1,0}; int rows,columns; queue<int> q; struct P { int x,y; }; P points[110]; int flag; int BFS() { int nStep; while(!q.empty()) { nStep=q.front(); q.pop(); for(int i=0;i<=nStep;i++) { points[i].x=q.front(); q.pop(); points[i].y=q.front(); q.pop(); } if(points[nStep].x<0 || points[nStep].x>=rows || points[nStep].y<0 || points[nStep].y>=columns) return nStep; for(int i=0;i<=nStep;i++) { if(i<nStep && points[nStep].x==points[i].x && points[nStep].y==points[i].y) { flag=i; return nStep-i; } } q.push(nStep+1); for(int i=0;i<=nStep;i++) { q.push(points[i].x); q.push(points[i].y); } int nDir=Map[points[nStep].x][points[nStep].y]; q.push(points[nStep].x+DirX[nDir-1]); q.push(points[nStep].y+DirY[nDir-1]); } } void OutputMap() { for(int i=0;i<rows;i++) { for(int j=0;j<columns;j++) { cout<<Map[i][j]; } cout<<endl; } } int main() { //cout << "Hello world!" << endl; //freopen("input.txt","r",stdin); int x,y; while(cin>>rows>>columns>>y) { while(!q.empty()) q.pop(); flag=-1; if(rows==0 && columns==0 && y==0)break; memset(Map,0,sizeof(Map)); //memset(vis,0,sizeof(vis)); x=0; char dir; for(int i=0;i<rows;i++) { for(int j=0;j<columns;j++) { cin>>dir; switch(dir) { case 'E': Map[i][j]=1; break; case 'S': Map[i][j]=2; break; case 'W': Map[i][j]=3; break; case 'N': Map[i][j]=4; } } } //OutputMap(); int step=0; q.push(step); q.push(x); q.push(y-1); //vis[x][y-1]=1; step=BFS(); if(flag==-1) cout<<step<<" step(s) to exit"<<endl; else cout<<flag<<" step(s) before a loop of "<<step<<" step(s)"<<endl; } return 0; }
注意二维数组的变化
[0][0], [0][1], [0][2].....[0][m-1]
[1][0], [1][1], [1][2].....[1][m-1]
[2][0], ......
...
[n-1][0], [n-1][1] ... .... [n-1][m-1]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。