20170908_hdu1495

debug:
中间过程出错，可以改写为函数
终止条件写错

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
using namespace std;

int mark[105][105][105];
int s,m,n;
int flag;

void dfs(int a, int b, int c, int step) {
    mark[a][b][c] = 1;
    if(b == s/2 || c == s/2) {
        cout << step << endl;
        flag = 1;
        return;
    }
    //a->b
    if(a <= (m-b)) {
        if(mark[0][b+a][c] == 0)
            dfs(0, b+a, c, step+1);
    }
    else {
        int t = a-(m-b);
        if(mark[t][b+a-t][c] == 0)
            dfs(t, b+a-t, c, step+1);
    }
    //a->c
    if(a <= (n-c)) {
        if(mark[0][b][c+a] == 0)
            dfs(0, b, c+a, step+1);
    }
    else {
        int t = a-(n-c);
        if(mark[t][b][c+a-t] == 0)
            dfs(t, b, c+a-t, step+1);
    }
    //b->a
    if(mark[a+b][0][c] == 0)
        dfs(a+b, 0, c, step+1);
    //b->c
    if(b <= (n-c)) {
        if(mark[a][0][b+c] == 0)
            dfs(a, 0, b+c, step+1);
    }
    else {
        int t = b - (n-c);
        if(mark[a][t][b+c-t] == 0)
            dfs(a, t, b+c-t, step+1);
    }
    //c->a
    if(mark[a+c][b][0] == 0)
        dfs(a+c, b, 0, step+1);
    //c->b
    if(c <= (m-b)) {
        if(mark[a][b+c][0])
            dfs(a, b+c, 0, step+1);
    }
    else {
        int t = c-(m-b);
        if(mark[a][b+c-t][t] == 0)
            dfs(a, b+c-t, t, step+1);
    }
    return;
}

int main() {
    while(scanf("%d %d %d",&s,&m,&n) && s && m && n) {
        memset(mark, 0, sizeof(mark));
        flag = 0;
        //cout << s << "   " << m << "   " << n << endl;
        if(s % 2 == 1)
            flag = 1;
        else
            dfs(s, 0, 0, 0);
        if(flag)
            cout << "NO" << endl;
    }
    return 0;
}

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
using namespace std;

int mark[105][105][105];
int s,m,n;
int flag;
struct state{
    int a;
    int b;
    int c;
    int step;
};


void bfs(state st) {
    state que[100005];
    memset(que, 0, sizeof(que));
    st.step = 0;
    int head = 0;
    int tail = 1;
    que[head] = st;
    mark[st.a][st.b][st.c] = 1;
    state now,next;
    while(head != tail) {
        now = que[head];
        if(now.b == s/2 || now.c == s/2) {
            cout << now.step << endl;
            if(now.a != 0)
                now.step++;
            flag = 0;
            return;
        }
        int aa,bb,cc;
        //a->b
        int t;
        if(now.a <= (m-now.b))
            t = 0;
        else t = now.a - (m-now.b);
        aa = t; bb = now.a+now.b-t; cc = now.c;
        if(mark[aa][bb][cc] != 1) {
            next.a = aa; next.b = bb; next.c = cc;
            next.step = now.step+1;
            que[tail++] = next;
            mark[aa][bb][cc] = 1;
        }
        //a->c
        if(now.a <= (n-now.c))
            t = 0;
        else t = now.a - n + now.c;
        aa = t; bb = now.b; cc = now.a+now.c-t;
        if(mark[aa][bb][cc] != 1) {
            next.a = aa; next.b = bb; next.c = cc;
            next.step = now.step+1;
            que[tail++] = next;
            mark[aa][bb][cc] = 1;
        }
        //b->a
        aa = now.b + now.a; bb = 0; cc = now.c;
        if(mark[aa][bb][cc] != 1) {
            next.a = aa; next.b = bb; next.c = cc;
            next.step = now.step+1;
            que[tail++] = next;
            mark[aa][bb][cc] = 1;
        }
        //b->c
        if(now.b <= (n-now.c))
            t = 0;
        else t = now.b-n+now.c;
        aa = now.a; bb = t; cc = now.b + now.c - t;
        if(mark[aa][bb][cc] != 1) {
            next.a = aa; next.b = bb; next.c = cc;
            next.step = now.step+1;
            que[tail++] = next;
            mark[aa][bb][cc] = 1;
        }
        //c->a
        aa = now.a + now.c; bb = now.b; cc = 0;
        if(mark[aa][bb][cc] != 1) {
            next.a = aa; next.b = bb; next.c = cc;
            next.step = now.step+1;
            que[tail++] = next;
            mark[aa][bb][cc] = 1;
        }
        //c->b
        if(now.c <= (m - now.b))
            t = 0;
        else t = now.c - m + now.b;
        aa = now.a; bb = now.b + now.c - t; cc = t;
        if(mark[aa][bb][cc] != 1) {
            next.a = aa; next.b = bb; next.c = cc;
            next.step = now.step+1;
            que[tail++] = next;
            mark[aa][bb][cc] = 1;
        }
        head++;
    }
}

int main() {
    while(scanf("%d %d %d",&s,&m,&n) && s && m && n) {
        memset(mark, 0, sizeof(mark));
        flag = 1;
        //cout << s << "   " << m << "   " << n << endl;
        state now;
        now.a = s;
        now.b = now.c = 0;
        if(s % 2 == 1)
            flag = 1;
        else
            bfs(now);
        if(flag)
            cout << "NO" << endl;
    }
    return 0;
}


#include <iostream>
#include <limits.h>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#include <queue>
using namespace std;

int mark[105][105][105];
int s,m,n;
int flag;
struct state{
    int a;
    int b;
    int c;
    int step;
};


void bfs(state st) {
    queue<state> que;
    st.step = 0;
    que.push(st);
    mark[st.a][st.b][st.c] = 1;
    state now,next;
    while(!que.empty()) {
        now = que.front();
        if((now.b == s/2 && now.a == s/2 )|| (now.a == s/2 && now.c == s/2) || (now.b == s/2 && now.c == s/2)) {
            cout << now.step << endl;
            flag = 0;
            return;
        }
        int aa,bb,cc;
        //a->b
        int t;
        if(now.a <= (m-now.b))
            t = 0;
        else t = now.a - (m-now.b);
        aa = t; bb = now.a+now.b-t; cc = now.c;
        if(mark[aa][bb][cc] != 1) {
            next.a = aa; next.b = bb; next.c = cc;
            next.step = now.step+1;
            que.push(next);
            mark[aa][bb][cc] = 1;
        }
        //a->c
        if(now.a <= (n-now.c))
            t = 0;
        else t = now.a - n + now.c;
        aa = t; bb = now.b; cc = now.a+now.c-t;
        if(mark[aa][bb][cc] != 1) {
            next.a = aa; next.b = bb; next.c = cc;
            next.step = now.step+1;
            que.push(next);
            mark[aa][bb][cc] = 1;
        }
        //b->a
        aa = now.b + now.a; bb = 0; cc = now.c;
        if(mark[aa][bb][cc] != 1) {
            next.a = aa; next.b = bb; next.c = cc;
            next.step = now.step+1;
            que.push(next);
            mark[aa][bb][cc] = 1;
        }
        //b->c
        if(now.b <= (n-now.c))
            t = 0;
        else t = now.b-n+now.c;
        aa = now.a; bb = t; cc = now.b + now.c - t;
        if(mark[aa][bb][cc] != 1) {
            next.a = aa; next.b = bb; next.c = cc;
            next.step = now.step+1;
            que.push(next);
            mark[aa][bb][cc] = 1;
        }
        //c->a
        aa = now.a + now.c; bb = now.b; cc = 0;
        if(mark[aa][bb][cc] != 1) {
            next.a = aa; next.b = bb; next.c = cc;
            next.step = now.step+1;
            que.push(next);
            mark[aa][bb][cc] = 1;
        }
        //c->b
        if(now.c <= (m - now.b))
            t = 0;
        else t = now.c - m + now.b;
        aa = now.a; bb = now.b + now.c - t; cc = t;
        if(mark[aa][bb][cc] != 1) {
            next.a = aa; next.b = bb; next.c = cc;
            next.step = now.step+1;
            que.push(next);
            mark[aa][bb][cc] = 1;
        }
        que.pop();
    }
}

int main() {
    while(scanf("%d %d %d",&s,&m,&n) && s && m && n) {
        memset(mark, 0, sizeof(mark));
        flag = 1;
        //cout << s << "   " << m << "   " << n << endl;
        state now;
        now.a = s;
        now.b = now.c = 0;
        if(s % 2 == 1)
            flag = 1;
        else
            bfs(now);
        if(flag)
            cout << "NO" << endl;
    }
    return 0;
}

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#include <queue>
using namespace std;

int a[17][17];
int b[17][17];
int c[17][17];
int ans[17][17];

void change(int i, int j) {
    if(b[i][j] == 1)
        b[i][j] = 0;
    else b[i][j] = 1;
}

void manage(int i, int j) {
    change(i,j);
    change(i-1,j);
    change(i,j-1);
    change(i+1,j);
    change(i,j+1);
    c[i][j] = 1;
}

int main() {
    int m,n;
    cin >> m;
    cin >> n;
    int max = 1;
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j)
            scanf("%d", &a[i][j]);
    for(int i = 0; i < n; ++i)
        max *= 2;
    int t = 300;
    for(int i = 0; i < max; ++i) {
        memset(c, 0, sizeof(c));
        int count = 0;
        for(int i = 1; i <= m; ++i)
            for(int j = 1; j <= n; ++j)
                b[i][j] = a[i][j];
        int cnt = 1;
        int tt = i;
        while(tt >= 1) {
            if((tt & 1) == 1) {
                manage(1,cnt);
                count++;
            }
            tt = tt >> 1;
        }
        int flag = 0;
        for(int i = 2; i <= m; ++i)
            for(int j = 1; j <= n; ++j) {
                if(b[i-1][j] == 1) {
                    manage(i,j);
                    count++;
                }
            }
        for(int j = 1; j <= n; ++j)
            if(b[m][j] == 1)
                flag = 1;
        if(t > count && flag == 0) {
            t = count;
            for(int i = 1; i <= m; ++i)
                for(int j = 1; j <= n; ++j)
                    ans[i][j] = c[i][j];
        }
    }
    if(t == 300)
        cout << "IMPOSSIBLE" << endl;
    else for(int i = 1; i <= m; ++i) {
        for(int j = 1; j <= n; ++j) {
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

最后编辑于：2017.12.10 07:00:25

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 202,406评论 5赞 475
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 84,976评论 2赞 379
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 149,302评论 0赞 335
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,366评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,372评论 5赞 363
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,457评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,872评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,521评论 0赞 256
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,717评论 1赞 295
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,523评论 2赞 319
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,590评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,299评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,859评论 3赞 306
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,883评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,127评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,760评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,290评论 2赞 342

20170908_hdu1495

推荐阅读更多精彩内容