简单搜索 kuangbin C D

C - Catch That Cow POJ - 3278

我心态崩了，现在来回顾很早之前写的简单搜索，好难啊，我怎么写不出来。

我开始把这个写成了dfs，还写搓了。。。

慢慢来吧。

这个题目很明显是一个很简单的搜索题，但是如果用dfs的话很容易出现问题，而且复杂度不低。

所以选择用bfs。

这个知道用bfs就应该比较简单了。

就是有三种走的方式，因为k最大为100000 所以我们要限制一下，不然会超时。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <vector>

#include <algorithm>

#include <iostream>

#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int maxn = 5e5 + ;

int n, k;

bool vis[maxn];

int d[maxn];

int t[] = { ,- };

void bfs(int x)

{

    queue<int>que;

    que.push(x);

    vis[x] = ;

    d[x] = ;

    while (!que.empty()) {

        int u = que.front(); que.pop();

        if (u > ) continue;

        if (u < ) continue;

        if(u==k)

        {

            printf("%d\n", d[k]);

            return;

        }

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

        {

            int tx;

            if (i == ) tx = u * ;

            else tx = u + t[i];

            if (vis[tx]) continue;

            if (u <  || u > ) continue;

            vis[tx] = ;

            d[tx] = d[u] + ;

            que.push(tx);

        }

    }

}

int main()

{

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

    bfs(n);

    return ;

}

D - Fliptile

POJ - 3279

看到这个题目，我真的心态崩了，这个题目好难啊，结果居然是简单搜索，我现在怀疑我这一年来干了什么。。。

感觉自己好菜。。。

算了，没办法，还是好好刷题吧。

这个题目真的很难。

因为我们每一个翻转，都会改变左右的色块，所以我们每次从下面的那块来使得上面的那块翻转，如果需要的话。

如果知道这一点了就稍微好做那么一点点了。

所以我们只要枚举第一块是怎么翻转的，这样子可以直接推出下面的是怎么翻转的。

知道这一点了，就很好写了，不过还是不一定可以写出代码，因为不知道怎么处理。

然后就看题解学习一下怎么写吧。

这个题目我有一个地方出现bug了，然后一直没有找到，就是一行有m个数，所以最多有m个1 所以枚举第一行的时候应该是1<<m

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <vector>

#include <algorithm>

#include <iostream>

#define inf 0x3f3f3f3f

using namespace std;

const int maxn = 1e5 + ;

int f[][], mp[][];

const int dx[] = { -,,,, };

const int dy[] = { ,-,,, };

int ans[][];

int n, m;

int getnum(int x, int y)//这个是由初始和翻转次数来判断这个面是0还是1

{

    int res = mp[x][y];

    for (int i = ; i < ; i++) {

        int tx = x + dx[i];

        int ty = y + dy[i];

        if (tx >=  && ty >=  && tx < n&&ty < m) res += f[tx][ty];

    }

    return res % ;

}

int cal() {

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

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

            if (getnum(i - , j)) {

                f[i][j] = ;

            }

        }

    }

    for (int i = ; i < m; i++) {

        if (getnum(n - , i)) return -;

    }

    int res = ;

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

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

            res += f[i][j];

        }

    }

    return res;

}

void solve() {

    int res = -;

    for (int i = ; i < ( << m); i++) {

        memset(f, , sizeof(f));

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

            f[][m - j - ] = i >> j & ;

        }

        int num = cal();

        if (num >=  && (res <  || num < res)) {

            res = num;

            memcpy(ans, f, sizeof(f));

        }

    }

    if (res == -) printf("IMPOSSIBLE\n");

    else {

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

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

                printf("%d%c", ans[i][j], j +  == m ? '\n' : ' ');

            }

        }

    }

}

int main() {

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

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

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

            scanf("%d", &mp[i][j]);

        }

    }

    solve();

    return ;

}

巴特西

简单搜索 kuangbin C D

C - Catch That Cow POJ - 3278

D - Fliptile

最新文章

热门文章