ZOJ - 4020 Traffic Light 【BFS】

题目链接

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4020

题意

给出一张地图以及起点和终点求是否能从起点走到终点如果能求出最小步数如果不能输出 -1

然后地图上的0表示在这个点只能上下走，，1 只能左右走

没走一步地图上每个1 都变成 0 每个0 都变成 1

思路

那么地图变化可以用步数 % 2 来求得如果步数 % 2 是 1 那么此时

1 就是 0 0 就是 1 如果步数 % 2 是 0 那么就按照原地图来算

因为 n 或者 m 特别大所以用 vector 来保存地图用一个 pair(int, int) 前者保存地图后者保存标记

AC代码

#include <cstdio>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <cmath>

#include <climits>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <numeric>

#include <sstream>

#include <iomanip>

#include <limits>

#define CLR(a) memset(a, 0, sizeof(a))

#define pb push_back

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

typedef pair<string, int> psi;

typedef pair<string, string> pss;

const double PI = acos(-1);

const double E = exp(1);

const double eps = 1e-30;

const int INF = 0x3f3f3f3f;

const int maxn = 1e3 + 5;

const int MOD = 1e9 + 7;

int Move[2][2][2]

{

    -1, 0,

     1, 0,

     0,-1,

     0, 1,

};

vector < vector <pii> > G;

vector <pii> tmp;

int sx, sy, ex, ey;

int ans;

int n, m;

struct Node

{

    int x, y, step;

}temp;

bool ok(int x, int y)

{

    if (x < 0 || x >= n || y < 0 || y >= m)

        return false;

    return true;

}

queue <Node> q;

void bfs()

{

    while (!q.empty())

    {

        int x = q.front().x;

        int y = q.front().y;

        int step = q.front().step;

        q.pop();

        if (x == ex && y == ey)

        {

            ans = step;

            return;

        }

        int d;

        if (step % 2)

            d = !G[x][y].first;

        else

            d = G[x][y].first;

        for (int i = 0; i < 2; i++)

        {

            temp.x = x + Move[d][i][0];

            temp.y = y + Move[d][i][1];

            if (ok(temp.x, temp.y) && G[temp.x][temp.y].second == 0)

            {

                temp.step = step + 1;

                q.push(temp);

                G[temp.x][temp.y].second = 1;

            }

        }

    }

}

int main()

{

    int t;

    cin >> t;

    while (t--)

    {

        G.clear();

        int num;

        scanf("%d%d", &n, &m);

        for (int i = 0; i < n; i++)

        {

            tmp.clear();

            for (int j = 0; j < m; j++)

            {

                scanf("%d", &num);

                tmp.pb(pii(num, 0));

            }

            G.pb(tmp);

        }

        scanf("%d%d%d%d", &sx, &sy, &ex, &ey);

        sx--, sy--, ex--, ey--;

        while (!q.empty())

            q.pop();

        temp.x = sx;

        temp.y = sy;

        temp.step = 0;

        q.push(temp);

        ans = -1;

        bfs();

        cout << ans << endl;

    }

}

巴特西

ZOJ - 4020 Traffic Light 【BFS】

最新文章

热门文章