您现在的位置是:首页 > 学习之路 > ACM||算法ACM||算法

POJ-3278 Catch That Cow

卞振伟2019-07-25【ACM||算法】人已围观

简介POJ-3278 Catch That Cow
BFS题
一维坐标,两种移动方式(+1 | *2),最快追上奶牛的时间
坑:不剪枝,教你做人.容易爆队列.不优化,过样例,也不能直接提交.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <climits>

using namespace std;

const int maxn = 20;
int n, m;
int mp[maxn][maxn];
int flip[maxn][maxn];
int ans[maxn][maxn];
int step[5][2] = {{0,1},{0,-1},{1,0},{-1,0},{0,0}};

bool check(int x,int y){
    if(x<0 || x>=n || y<0 || y>=m)
        return false;
    return true;
}

bool isFlip(int x, int y){
    int color = mp[x][y];
    for(int i = 0; i < 5; ++i){
        int cur_x = x+step[i][0];
        int cur_y = y+step[i][1];
        if(flip[cur_x][cur_y] && check(cur_x, cur_y))
            color++;
    }
    return color%2;
}

int getFlipNum(){
    int sum = 0;
    for(int i = 0; i < m; ++i)
        if(flip[0][i])
            sum++;
    for(int i = 1; i < n; ++i)
        for(int j = 0; j < m; ++j)
            if(isFlip(i-1, j)){
                flip[i][j] = 1;
                sum++;
            }
    for(int i = 0; i < m; ++i)
        if(isFlip(n-1, i))
            return -1;
    return sum;
}

int MIN = INT_MAX;

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            scanf("%d", &mp[i][j]);
    for(int i = 0; i < 1<<m; ++i){
        memset(flip, 0, sizeof(flip));
        for(int j = 0; j < m; ++j)
            flip[0][m-j-1] = i>>j&1;
        int cot = getFlipNum();
        if(cot == -1)
            continue;
        if(MIN > cot){
            MIN = cot;
            memcpy(ans, flip, sizeof(flip));
        }
    }
    if(MIN == INT_MAX)
        printf("IMPOSSIBLE");
    else{
        for(int i = 0; i < n; ++i){
            if(i)
                printf("\n");
            for(int j = 0; j < m; ++j){
                if(j)
                    printf(" ");
                printf("%d", ans[i][j]);
            }
        }
    }
    return 0;
}

Tags:ACM   编程   个人   题解   算法   C|C++

很赞哦! ()

上一篇:POJ-2251 Dungeon Master

下一篇:POJ-3279 Fliptile

文章评论

站点信息

  • 建站时间:2018-11-25
  • 网站程序:帝国CMS7.5
  • 文章统计:118篇文章
  • 标签管理标签云
  • 统计数据百度统计
  • 网站地图XML网站地图
  • 微信公众号:扫描二维码,关注我的公众号
  • GitHub:扫描二维码,关注我的GitHub

客服在线

QQ客服

客服微信扫码

服务时间

周一至周日 9:00-21:00