HDU 5335 Walk Out

题意：在一个只有0和1的矩阵里，从左上角走到右下角，每次可以向四个方向走，每个路径都是一个二进制数，求所有路径中最小的二进制数。

解法：先bfs求从起点能走到离终点最近的0，那么从这个点起只向下或向右走就可以获得位数最少的二进制数，然后贪心的想，如果后或下有0就一定走0，没0就把1都看一遍，以之前搜到的0做起点，一层一层遍历可行路径，直到终点。

代码：

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string>

#include<string.h>

#include<math.h>

#include<limits.h>

#include<time.h>

#include<stdlib.h>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define LL long long

using namespace std;

int n, m;

bool vis[1005][1005];

char maze[1005][1005];

struct node

{

    int x, y;

    node(int x, int y) : x(x), y(y) {}

    node() {}

};

queue <node> q;

vector <node> v[2];

int maxn = 0;

int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};

void bfs()

{

    q.push(node(0, 0));

    vis[0][0] = 1;

    if(maze[0][0] == '1')

    {

        q.pop();

        return ;

    }

    while(!q.empty())

    {

        node tmp = q.front();

        q.pop();

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

        {

            int tx = tmp.x + dir[i][0], ty = tmp.y + dir[i][1];

            if(tx >= 0 && tx < n && ty >= 0 && ty < m && !vis[tx][ty] && maze[tx][ty] == '0')

            {

                vis[tx][ty] = 1;

                maxn = max(maxn, tx + ty);

                q.push(node(tx, ty));

            }

        }

    }

}

int main()

{

    int T;

    while(~scanf("%d", &T))

    {

        while(T--)

        {

            maxn = 0;

            memset(vis, 0, sizeof vis);

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

                v[i].clear();

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

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

                scanf("%s", maze[i]);

            bfs();

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

            {

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

                {

                    if(vis[i][j] && (i + j == maxn))

                        v[0].push_back(node(i, j));

                }

            }

            int cnt = 0;

            int flag2 = 1;

            string ans;

            if(maze[0][0] == '1')

                ans += '1';

            else

                ans += '0';

            while(1)

            {

                int len = v[cnt].size();

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

                {

                    if((v[cnt][i].x == n - 1) && (v[cnt][i].y == m - 1))

                    {

                        flag2 = 0;

                        break;

                    }

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

                    {

                        int tx = v[cnt][i].x + dir[j][0], ty = v[cnt][i].y + dir[j][1];

                        if(tx >= 0 && tx < n && ty >= 0 && ty < m && !vis[tx][ty] && maze[tx][ty] == '0')

                        {

                            vis[tx][ty] = 1;

                            v[!cnt].push_back(node(tx, ty));

                        }

                    }

                }

                if(!flag2) break;

                if(v[!cnt].size() == 0)

                {

                    ans += '1';

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

                    {

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

                        {

                            int tx = v[cnt][i].x + dir[j][0], ty = v[cnt][i].y + dir[j][1];

                            if(tx >= 0 && tx < n && ty >= 0 && ty < m && !vis[tx][ty] && maze[tx][ty] == '1')

                            {

                                vis[tx][ty] = 1;

                                v[!cnt].push_back(node(tx, ty));

                            }

                        }

                    }

                }

                else

                    ans += '0';

                v[cnt].clear();

                cnt = !cnt;

            }

            int len = ans.size();

            int flag1 = 1;

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

            {

                if((ans[i] == '0') && flag1) continue;

                flag1 = 0;

                printf("%c", ans[i]);

            }

            if(flag1)

                printf("0");

            puts("");

        }

    }

    return 0;

}

不知道为什么一直MLE……换了个写法重写了一下才过……

巴特西

HDU 5335 Walk Out

最新文章

热门文章