Submission #162942

---

Source Code Expand

#include <string>
#include <iostream>
#include <vector>
#include <complex>
#include <queue>
#include <utility>
using namespace std;

enum{EEmpty=0,EWall,EStart,EGoal};

inline int g_c(int x,int y,int C){ return x+C*y; }
inline int g_c(complex<int> c,int C){ return c.real()+C*c.imag(); }

int main(void){
	int R,C,_x,_y;

	cin >> R >> C;
	cin >> _y >> _x;
	complex<int> st(_x-1,_y-1);
	cin >> _y >> _x;
	complex<int> gl(_x-1,_y-1);

	vector<int> c(R*C),ans(R*C,-1);
	for(int i=0;i<R;++i){
		std::string line;
		cin >> line;
		for(int j=0;j<C;++j){
			if(line[j]=='.'){ c[i*C+j] = EEmpty;}
			else{ c[i*C+j] = EWall;}
		}
	}
	c[g_c(st,C)] = EStart;
	c[g_c(gl,C)] = EGoal;

	queue<complex<int> > now,next;
	now.push( st );
	int gen = 0;
	while(!now.empty()){
		while(!now.empty()){
			complex<int> nc = now.front(),t;
			now.pop();
			//now
			ans[ g_c(nc,C) ] = gen;
			if(nc==gl){
				cout << gen << endl; return 0;
			}
			//next
			t=nc; t-=complex<int>(0,1);
			if(t.imag()>=0 && c[g_c(t,C)]!=EWall && ans[g_c(t,C)]==-1){ next.push(t);ans[g_c(t,C)]=-2; }
			t=nc; t-=complex<int>(1,0);
			if(t.real()>=0 && c[g_c(t,C)]!=EWall && ans[g_c(t,C)]==-1 ){ next.push(t);ans[g_c(t,C)]=-2; }
			t=nc; t+=complex<int>(0,1);
			if(t.imag()<R && c[g_c(t,C)]!=EWall && ans[g_c(t,C)]==-1 ){ next.push(t);ans[g_c(t,C)]=-2; }
			t=nc; t+=complex<int>(1,0);
			if(t.real()<C && c[g_c(t,C)]!=EWall && ans[g_c(t,C)]==-1 ){ next.push(t);ans[g_c(t,C)]=-2; }
		}

		swap(now,next);
		++gen;
	}

	//string in;
	//cin >> in;
	//if(in.length() > 1){
	//	cout << in.substr(0,in.length()-1) << endl;
	//}else if(in[0]!='a'){
	//	cout << static_cast<char>(in[0]-1) << endl;
	//}else{
	//	cout << "-1" << endl;
	//}
	
	return 0;
}

Submission Info

Judge Result