幅優先探索(BFS)で迷路の最短経路

人材獲得作戦・４ 試験問題ほか: 人生を書き換える者すらいた。

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef struct {
	int x, y;
} px;
int main(){
	vector<vector<char> > v;
	vector<char> li;
	px st, gl = {-1, -1};
	int ylen, xlen;
	const char wall = '*', route = '$';
	char c;
	int fst = 1;
	li.push_back(wall);
	while(c = getchar(), 1){
		if(c == 'S'){
			st.y = v.size();
			st.x = li.size();
		}
		if((c == '\n' || c == EOF) && li.size() != 1){
			li.push_back(wall);
			if(fst){
				vector<char> t(li.size(), wall);
				v.push_back(t);
				fst = 0;
			}
			v.push_back(li);
			li.clear();
			li.push_back(wall);
		}else{
			li.push_back(c);
		}
		if(c == EOF){
			vector<char> t(v[0].size(), wall);
			v.push_back(t);
			break;
		}
	}
	ylen = v.size();xlen = v[0].size();
	px _px = {-1, -1};
	vector<vector<px> > f(ylen, vector<px>(xlen, _px));
	queue<px> q;
	q.push(st);
	f[st.y][st.x] = st;
	while(!q.empty()){
		const char ta[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
		px cur = q.front(); q.pop();
		if(v[cur.y][cur.x] == 'G'){
			gl = cur;
			break;
		}
		for(int i = 0; i < 4; i++){
			int y = cur.y + ta[i][0], x = cur.x + ta[i][1];
			if(v[y][x] != wall && f[y][x].x == -1){
				px t;
				t.y = y;t.x = x;
				q.push(t);
				t.y = cur.y;t.x = cur.x;
				f[y][x] = t;
			}
		}
	}
	if(gl.x == -1){
		puts("There's no goal");
		return 1;
	}
	for(int y = gl.y, x = gl.x; y = f[y][x].y, x = f[y][x].x, 1; ){
		if(st.y == y && st.x == x) break;
		v[y][x] = route;
	}
	for(int i = 1; i < ylen - 1; i++){
		for(int j = 1; j < xlen - 1; j++)
			putchar(v[i][j]);
		putchar('\n');
	}
	return 0;
}

コードの9割方は電子辞書の上のテキストエディタで書きました。

追記:あれ…なんかバグってる?まあ暇な時にデバッグします…