hdu4740【杭州网赛、模拟、有点搜索？】

当时看了这题就感觉so easy。。。本来不想写的，后来感觉是不是可以练一下搜索水平。。

比赛时有人过了就没写。比赛完了写一下。

实现还不是那么顺利，囧

本来自己以为这题能练下搜索，其实DFS、BFS都没用到，也许模拟中有点搜索吧。

还是类似方格的东西把外围也设置成未标记要好的多，做题多了也许就有这种感觉了吧。

还有自己忽略了驴老虎前面是已经走过的路也可以转弯。 BS！！

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

#define clr(x) memset(x, 0, sizeof(x))

using namespace std;

const int maxn = 1200;

int dv[maxn][maxn], tv[maxn][maxn];

int n, temp;

//碰到已经走过的点也会转向  不仅是撞墙时。

int main()

{

    while(scanf("%d", &n) != EOF)

    {

        if(!n) break;

        memset(dv, -1, sizeof(dv));

        memset(tv, -1, sizeof(tv));

        int a2, b2, c2, a1, b1, c1, ans;

        scanf("%d%d%d",&a1, &b1, &c1);

        a1++; b1++;

        scanf("%d%d%d",&a2, &b2, &c2);

        a2++; b2++;

        ans = 0;

        for(int i = 1; i <= n; i++)  //防止界外。 外围都要包一层

            for(int j = 1; j <= n; j++)

            {

                dv[i][j] = 0;

                tv[i][j] = 0;

            }

        dv[a1][b1] = 1; tv[a2][b2] = 1;

        while(true)

        {

            int ok1 = 0, ok2 = 0, temp;

            if(a1 == a2 && b1 == b2) break;

            if(c1 == 0) // east

            {

                temp = b1 + 1;

                if(!dv[a1][temp])

                {

                    ++b1;

                    ok1 = 1;

                    dv[a1][temp] = 1;

                }

                else if(!dv[a1+1][b1])

                {

                    ++a1;

                    ok1 = 1;

                    c1 = 1;

                    dv[a1][b1] = 1;

                }

            }

            else if(c1 == 1) //south

            {

                temp = a1 + 1;

                if(!dv[temp][b1])

                {

                    ++a1;

                    ok1 = 1;

                    dv[temp][b1] = 1;

                }

                else if(!dv[a1][b1-1])

                {

                    --b1;

                    ok1 = 1;

                    c1 = 2;

                    dv[a1][b1] = 1;

                }

            }

            else if(c1 == 2) //west

            {

                temp = b1 - 1;

                if(!dv[a1][temp])

                {

                    --b1;

                    ok1 = 1;

                    dv[a1][temp] = 1;

                }

                else if(!dv[a1-1][b1])

                {

                    --a1;

                    ok1 = 1;

                    c1 = 3;

                    dv[a1][b1] = 1;

                }

            }

            else if(c1 == 3) //north

            {

                temp = a1 - 1;

                if(!dv[temp][b1])

                {

                    --a1;

                    ok1 = 1;

                    dv[temp][b1] = 1;

                }

                else if(!dv[a1][b1+1])

                {

                    ++b1;

                    ok1 = 1;

                    c1 = 0;

                    dv[a1][b1] = 1;

                }

            }

            if(c2 == 0) // east

            {

                temp = b2 + 1;

                if(!tv[a2][temp])

                {

                    ++b2;

                    ok2 = 1;

                    tv[a2][temp] = 1;

                }

                else if(!tv[a2-1][b2])

                {

                    --a2;

                    ok2 = 1;

                    c2 = 3;

                    tv[a2][b2] = 1;

                }

            }

            else if(c2 == 1) //south

            {

                temp = a2 + 1;

                if(!tv[temp][b2])

                {

                    ++a2;

                    ok2 = 1;

                    tv[temp][b2] = 1;

                }

                else if(!tv[a2][b2+1])

                {

                    ++b2;

                    ok2 = 1;

                    c2 = 0;

                    tv[a2][b2] = 1;

                }

            }

            else if(c2 == 2) //west

            {

                temp = b2 - 1;

                if(!tv[a2][temp])

                {

                    --b2;

                    ok2 = 1;

                    tv[a2][temp] = 1;

                }

                else if(!tv[a2+1][b2])

                {

                    ++a2;

                    ok2 = 1;

                    c2 = 1;

                    tv[a2][b2] = 1;

                }

            }

            else if(c2 == 3) //north

            {

                temp = a2 - 1;

                if(!tv[temp][b2])

                {

                    --a2;

                    ok2 = 1;

                    tv[temp][b2] = 1;

                }

                else if(!tv[a2][b2-1])

                {

                    --b2;

                    ok2 = 1;

                    c2 = 2;

                    tv[a2][b2] = 1;

                }

            }

            if(ok1 == 0 && ok2 == 0)

            {

                ans = -1; break;

            }

        }

        if(ans == -1) printf("-1\n");

        else printf("%d %d\n", a1-1, b1-1);

    }

    return 0;

}

自己要是想缩短代码长度其实可以设个函数。

再看看THU的代码。。有 1 -1 0 0 这种东西。。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<string>

using namespace std;

const int MAX_N = 1000 + 10;

int n;

//E,S,W,N

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

struct Walker {

    int x, y, d, turn;

    bool active;

    bool vis[MAX_N][MAX_N]; //where had he visited

    void read(int turn) {

        this->turn = turn;

        cin >> x >> y >> d;

        active = true;

        memset(vis, 0, sizeof vis);

    }

    bool check(int r, int c) {

        return r >= 0 && r < n && c >= 0 && c < n && !vis[r][c];

    }

    void walk() { //can walk?

        //go stright

        if (check(x + dx[d], y + dy[d])) {

            x += dx[d], y += dy[d];

            goto end;

        }

        d = (d + turn) % 4;

        if (check(x + dx[d], y + dy[d])) {

            x += dx[d], y += dy[d];

            goto end;

        }

        active = false;        //dead >_<

        return;

        end: {

        }

        vis[x][y] = true;

    }

};

Walker A, B;

int main() {

    for (;;) {

        cin >> n;

        if (n == 0)

            break;

        A.read(1);

        B.read(3);

        A.vis[A.x][A.y] = true;

        B.vis[B.x][B.y] = true;

        for (;;) {

            if (!A.active && !B.active)

                break;        //end!

            if (A.x == B.x && A.y == B.y) {

                cout << A.x << " " << A.y << endl;

                goto end;

            }

            if (A.active) {

                A.walk();

            }

            if (B.active) {

                B.walk();

            }

        }

        cout << -1 << endl;

        end: {

        }

    }

}

巴特西

hdu4740【杭州网赛、模拟、有点搜索？】

最新文章

热门文章