Submission #6867033


Source Code Expand

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<float.h>
#include<tuple>
#include<string.h>
#include<iomanip>
#include<stack>
#include<queue>

using namespace std;
#define ll long long
#define rep(i,n) for(ll i=0;i<n;i++)
#define ALLOF(c) (c).begin(), (c).end()
#define Pa pair<ll,ll>
const ll mod=10e9+7;
const ll INF=10e12;
const ll inf=-1;
ll ABS(ll a){return max(a,-a);}

ll R,C,sy,sx,gy,gx;
char map[509][509];
ll d[509][509];

ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};

ll bfs(void){
    queue<Pa> que;
    que.push(Pa(sy,sx));
    d[sy][sx]=0;
    
    while(que.size()>0){
        Pa p=que.front();
        que.pop();
        
        if(p.first==gy && p.second==gx) break;
        rep(i,4){
            ll ny=p.first+dy[i];
            ll nx=p.second+dx[i];
            if (0 <= nx && nx < C && 0 <= ny && ny < R && map[ny][nx] != '#' && d[ny][nx] == INF) {
                que.push(Pa(ny, nx));
                d[ny][nx] = d[p.first][p.second] + 1;
            }
        }
    }
    return d[gy][gx];
}

int main(void){
    cin>>R>>C>>sy>>sx>>gy>>gx;
    sy--;
    sx--;
    gy--;
    gx--;
    rep(i,R){
        rep(j,C){
            cin>>map[i][j];
            d[i][j]=INF;
        }
    }
  ll ans=bfs();
    cout<<ans<<endl;
    return 0;
}

Submission Info

Submission Time
Task A - 幅優先探索
User cc226158
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1412 Byte
Status AC
Exec Time 3 ms
Memory 640 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 25
Set Name Test Cases
Sample subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt
All subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt
Case Name Status Exec Time Memory
subtask0_sample01.txt AC 1 ms 256 KB
subtask0_sample02.txt AC 1 ms 256 KB
subtask0_sample03.txt AC 1 ms 512 KB
subtask1_01.txt AC 1 ms 512 KB
subtask1_02.txt AC 1 ms 512 KB
subtask1_03.txt AC 1 ms 512 KB
subtask1_04.txt AC 1 ms 512 KB
subtask1_05.txt AC 1 ms 512 KB
subtask1_06.txt AC 1 ms 512 KB
subtask1_07.txt AC 1 ms 256 KB
subtask1_08.txt AC 1 ms 512 KB
subtask1_09.txt AC 1 ms 512 KB
subtask1_10.txt AC 1 ms 512 KB
subtask1_11.txt AC 1 ms 512 KB
subtask1_12.txt AC 1 ms 512 KB
subtask1_13.txt AC 1 ms 512 KB
subtask1_14.txt AC 1 ms 512 KB
subtask1_15.txt AC 1 ms 512 KB
subtask1_16.txt AC 3 ms 640 KB
subtask1_17.txt AC 1 ms 512 KB
subtask1_18.txt AC 1 ms 512 KB
subtask1_19.txt AC 1 ms 512 KB
subtask1_20.txt AC 1 ms 512 KB
subtask1_21.txt AC 1 ms 512 KB
subtask1_22.txt AC 1 ms 512 KB