CZYZ Training Day1 (8.7)

C : map
Diff : 2(Easy)
Comment :
Yeah, it’s very very easy.But, …

Why?

Hmm, this is std code.

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> P;

int h, w;
string s[600];

int dist[600][600];

void solve () {
    int INF = h * w + 5;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            dist[i][j] = INF;
        }
    }
    dist[0][0] = 0;

    queue<P> que;
    que.push(P(0, 0));

    while (!que.empty()) {
        P pos = que.front();
        int cx = pos.first, cy = pos.second;
        que.pop();

        P dirs[4] = {
            {-1,  0},
            {+1,  0},
            { 0, -1},
            { 0, +1}
        };
        for (int i=0;i<4;i++) {
            int nx = cx +  dirs[i].first;
            int ny = cy + dirs[i].second;

            if (nx < 0 || nx >= h) continue;
            if (ny < 0 || ny >= w) continue;

            if (dist[nx][ny] != INF) continue;

            if (s[cx][cy] == s[nx][ny]) continue;

            dist[nx][ny] = dist[cx][cy] + 1;
            que.push(P(nx, ny));
        }
    }

    int result = dist[h - 1][w - 1];
    if (result != INF) {
        cout << result << endl;
    } else {
        cout << "-1" << endl;
    }
}

int main (void) {
    freopen("map.in","r",stdin);
    freopen("map.out","w",stdout);
    cin >> h >> w;
    for (int i = 0; i < h; i++) {
        cin >> s[i];
    }

    solve();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

It’s my code…

#include <bits/stdc++.h>
using namespace std;

#define vec vector<vector<int> >
int D[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

struct pos {
    int y, x;
};

bool operator< (pos a, pos b) {
    if (a.y != b.y) return a.y < b.y;
    return a.x < b.x; 
}

bool operator== (pos a, pos b) {return a.y==b.y&&a.x==b.x;}

int bfs(vec g, int cy, int cx, int ey, int ex) {
    deque<pos> pq;
    map<pos, pos> parents;
    set<pos> accessed;
    pq.push_back(pos{cy, cx});
    int _=0;
    //cout << g[0].size() << endl;
    while(!pq.empty()) {
        for (int i=0;i<4;i++) {
            int ky = pq.front().y + D[i][0], kx = pq.front().x + D[i][1];
            //cout << ky << ' ' << kx << '|';
            if (ky<0||ky>=g.size()||kx<0||kx>=g[0].size()) continue;
            if (accessed.find(pos{ky, kx}) != accessed.end()) continue;
            if (g[pq.front().y][pq.front().x]+g[ky][kx] != 1) continue;
            parents[pos{ky, kx}] = pq.front();
            pq.push_back(pos{ky, kx});
        }
        //for (int i=0;i<pq.size();i++) cout << endl << pq[i].y << ' ' << pq[i].x << endl;
        //cout << endl;
        accessed.insert(pq.front());
        pq.pop_front();
    }
    if (accessed.find(pos{ey, ex}) == accessed.end()) return -1;
    pos current = pos{ey, ex};
    int step = 0;
    while (!(current == pos{cy, cx})) {
        step++;
        current = parents[current];
    }
    return step;
}

int main() {
    freopen("map.in", "r", stdin);
    freopen("map.out", "w", stdout);
    int h, w;cin >> h >> w;
    vector<vector<int> > grid;
    grid.resize(h);
    for (int i=0;i<h;i++) {
        grid[i].resize(w);
        string l;cin >> l;
        for (int j=0;j<w;j++) {
            if (l[j]=='.') grid[i][j] = 0;
            else grid[i][j]=1;
        }
    }
    cout << bfs(grid, 0, 0, h-1, w-1);
}

Wait.

std code int dist[600][600]
my code set accessed;
my idea set.find() O(log2N) | dist[i][j] O(1)

OHHHHH.Corrent it now!!!

…?????
one line in latest code accessed[cy][cx] = 1;
change to accessed[cy][cx] = 0;

…¿¿¿