Submission #163367

---

Source Code Expand

//
//  main.cpp
//  ARCH
//
//  Created by 鹿島 悠 on 2014/04/20.
//  Copyright (c) 2014年 鹿島 悠. All rights reserved.
//

#include <iostream>
#include <queue>
#include <set>
#include <string>


using namespace std;

int R,C,sx,sy,gy,gx;

int main(int argc, const char * argv[])
{

    cin >> R >> C >> sy >> sx >> gy >> gx;
    sx--;sy--;gx--;gy--;

    //cout << R << C << sy << sx << gy << gx << endl;

    string c[R];
    int dp[R][C];
    int INF = 10000000;
    for (int i=0; i < R; i++)
    	for (int j=0;j<C;j++)
    		dp[i][j] = INF;

    for (int i=0; i < R; i++)
        cin >> c[i];

    queue< pair<int, int> > que;

    que.push(make_pair(sy, sx));
    dp[sy][sx] = 0;


    int vx[4] = { -1, 0, 1, 0 };
    int vy[4] = { 0,  1, 0, -1 };

    //cout << R << C << sy << sx << gy << gx << endl;

    while (!que.empty()) {
    	auto cur = que.front();

    	que.pop();
    	auto cur_step = dp[cur.first][cur.second];


    	for (int i=0; i < 4; i++) {
    		auto ny = vy[i] + cur.first;
    		auto nx = vx[i] + cur.second;

    		//cout << ny << ' ' << nx << endl;
    		if (ny == gy && nx == gx) {
    			cout << cur_step+1 << endl;
    			return 0;
    		}
    		else if (ny >= 0 && nx >= 0 && ny < R && nx < C && c[ny][nx] != '#') {
    			auto next = make_pair(ny, nx);
    			if (dp[ny][nx] == INF) {
    				dp[ny][nx] = cur_step+1;
    				que.push(next);
    			}
    		}
    	}
    }



    cout << -1 << endl;
    return 0;
}

Submission Info

Judge Result