提出 #71689990

---

ソースコード 拡げる

//#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include <stdlib.h>
#include<string>
#include<math.h>
#include<sstream>
#include<set>
#include<math.h>
#include <algorithm>
#include<map>
#include <numeric>
#include <sstream>
#include <iomanip>
#include<tuple>
#include <bitset>
#include <queue>
#include <iomanip>
#include <stack>
#include<time.h>
#include <unordered_set>
#include <random>
using namespace::std;
#define RANDMAX  100000
#define ll long long 
#define lint long long int
#define ldouble long double
#define ALL(a)  (a).begin(),(a).end()
using ve = vector<lint>;

vector<vector<int>> map2;
//
using Gra = vector<vector<lint>>;
using sve = vector<string>;
//  


//cout << std::fixed << std::setprecision(15)<< ans;//�����_
//

// 
//<stack>//�ォ��
// box.push()
// box.pop()
// box.top()
// 
// <queue>������
// box.push()
// box.front()
// box.pop()
// 
// <set>
// ite=g2.lower_bound(r) set�񕔒T��
// distance(ls.begin(), ite);�T��������̈���
// advance() �͋ɗ͎g��Ȃ����ƁI�I�@***************************************
// g2.count() set()���̌�
// lower_bound(a.begin(),a.end(),a[i])
// box.size()
// 
// <vector>
// vector<int>
// lower_bound(a.begin(),a.end(),a[i])
// vector<vector<lint>> v(2, vector<lint>(3)) -> v.at(1).at(2);
// next_permutation(aaa.begin(), aaa.end()) �x�N�^�[�̑g�ݍ��킹
//
//<2���T���@�`�蓮�����΁`>
// int binary_search(int key) {
//    int left = 0, right = (int)a.size() - 1; // �z�� a �̍��[�ƉE�[
//    while (right >= left) {
//        int mid = left + (right - left) / 2; // ��Ԃ̐^��
//        if (a[mid] == key) return mid;
//        else if (a[mid] > key) right = mid - 1;
//        else if (a[mid] < key) left = mid + 1;
//    }
//    return -1;
// }
// 
// <bit�S�T��>
//�@bitset<60> bs(n);
//
//�{��swap����Ƃ��͔��̔ԍ���ς���






/*	par=time_check(nh, nm);
    nh = par.first; nm = par.second;*/
pair<lint, lint> time_check(int h, int m) {
    while (m >= 60) {
        h += 1;
        m -= 60;
    }
    while (m < 0) {
        h -= 1;
        m += 60;
    }
    return make_pair(h, m);
}


std::random_device seed_gen;
uint32_t get_rand() {
    // ����������i�����ɃV�[�h���w��”\�j
    static std::mt19937 mt32(seed_gen());

    // [0, (2^32)-1] �̈�l���z�����𐶐�
    return mt32();
}

class ansd {
public:
    int p;
    int x;
    int y;
};

class zahyo {
public:
    int x;
    int y;
};


int main() {
    lint h, w,nh,nw,an,ans=-1;
    cin >> h >> w;
    vector<string >ma(h);
    vector<vector<bool>>ok(h,vector<bool>(w));
    vector<set<pair<int, int>>>wap('z' - 'a' + 1);
    for (lint i = 0; i < h; i++)  {
        cin >> ma[i];
        for (lint j = 0; j < w; j++) {
            if (ma[i][j] >= 'a' && ma[i][j] <= 'z') {
                wap[ma[i][j] - 'a'].insert(make_pair(i, j));
            }
        }
    }
    queue<tuple<int, int,int>> box;
        //      h   w
    tuple<int, int,int> res;
    set<char> mozi;
    box.push({ 0,0,0 });
    while (box.size() != 0) {
        res = box.front();
        box.pop();
        nh = get<0>(res);
        nw = get<1>(res);
        an = get<2>(res);
        if (nh == h - 1 && nw == w - 1) {
            ans = an; break;
        }
        if (ma[nh][nw] >= 'a' && ma[nh][nw] <= 'z') {
            if (mozi.find(ma[nh][nw]) == mozi.end()){
                for (auto v : wap[ma[nh][nw] - 'a']) {
                    if (ok[v.first][v.second] == 0) {
                        box.push({ v.first,v.second,an + 1 });
                        ok[v.first][v.second] = 1;
                    }
                }
                mozi.insert(ma[nh][nw]);
            }
        }
        if (nh != 0) {
            if (ok[nh-1][nw] == 0&& ma[nh - 1][nw] !='#') {
                box.push({ nh-1,nw,an+1 });
                ok[nh-1][nw] = 1;
            }
        }
        if (nh != h-1) {
            if (ok[nh + 1][nw] == 0 && ma[nh + 1][nw] != '#') {
                box.push({ nh + 1,nw,an+1 });
                ok[nh +1][nw] = 1;
            }
        }
        if (nw != 0) {
            if (ok[nh][nw-1] == 0 && ma[nh ][nw-1] != '#') {
                box.push({ nh,nw-1,an+1 });
                ok[nh][nw-1] = 1;
            }
        }
        if (nw != w - 1) {
            if (ok[nh][nw+1] == 0 && ma[nh][nw+1] != '#') {
                box.push({ nh,nw+1,an+1 });
                ok[nh][nw+1] = 1;
            }
        }
    }
    cout << ans;
}

提出情報

ジャッジ結果