迷路解析

kerio.hpp

// kerio.hpp
#include<vector>
#include<queue>
#include<iostream>
#include<fstream>

#define pY(x){dy.push_back(x);}
#define pX(xx){dx.push_back(xx);}

class Keiro{
private:
	int sy,sx;
        std::vector<int> dy;
        std::vector<int> dx;
	std::vector<std::string> maze;	
  
        struct Point{
        	int y,x;
	        Point(int y=0,int x=0):y(y),x(x){}
        };
public:
	Keiro(const char* args=NULL)
	{
                pY(0);pY(1);pY(0);pY(-1);
                pX(1);pX(0);pX(-1);pX(0);
		std::string line;
                std::ifstream ifs(args);
                while(ifs && getline(ifs,line))
			maze.push_back(line);
                sy=maze.size();
                sx=maze[0].length();
	}

	void trans()
	{
		std::queue<Point> q;
                std::vector<std::vector<int> >stp(sy,std::vector<int>(sx,-1));
		for(int i=0; i<sy; i++){
			for(int k=0; k<sx; k++){
				if(maze[i][k]=='S'){
					q.push(Point(i,k));
					stp[i][k]=-2;
				}
			}
		}
		Point goal;
		while(!q.empty()){
			Point p(q.front());
			q.pop();
			if(maze[p.y][p.x]=='G'){
				goal=p;
				break;
			}
			for(int i=0; i<4; i++){
				int xxx(p.x+dx[i]);
				int yyy(p.y+dy[i]);

				if(maze[yyy][xxx]!='*'&&stp[yyy][xxx]==-1){
					q.push(Point(yyy,xxx));
					stp[yyy][xxx]=i;
				}
			}
		}
		int gy(goal.y);
		int gx(goal.x);
		while(true){
			int i(stp[gy][gx]^2);
			gy+=dy[i];
			gx+=dx[i];
			if(maze[gy][gx]=='S')break;
			maze[gy][gx]='$';
		}
		for(int i=0; i<sy; i++)
			std::cout<<maze[i]<<std::endl;
	}
};