20170908_hdu1495

debug:
中間過程出錯(cuò)，可以改寫為函數(shù)
終止條件寫錯(cuò)

#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

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末泻云，一起剝皮案震驚了整個(gè)濱河市粱快，隨后出現(xiàn)的幾起案子汤徽，更是在濱河造成了極大的恐慌劫侧，老刑警劉巖萌踱，帶你破解...
沈念sama閱讀 222,627評(píng)論 6贊 517
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件谋国，死亡現(xiàn)場(chǎng)離奇詭異槽地，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 95,180評(píng)論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門捌蚊，熙熙樓的掌柜王于貴愁眉苦臉地迎上來集畅，“玉大人，你說我怎么就攤上這事逢勾∧嫡” “怎么了？”我有些...
開封第一講書人閱讀 169,346評(píng)論 0贊 362
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵溺拱，是天一觀的道長(zhǎng)逃贝。經(jīng)常有香客問我，道長(zhǎng)迫摔，這世上最難降的妖魔是什么沐扳？我笑而不...
開封第一講書人閱讀 60,097評(píng)論 1贊 300
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮句占，結(jié)果婚禮上沪摄，老公的妹妹穿的比我還像新娘。我一直安慰自己纱烘，他們只是感情好杨拐，可當(dāng)我...
茶點(diǎn)故事閱讀 69,100評(píng)論 6贊 398
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著擂啥，像睡著了一般哄陶。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上哺壶，一...
開封第一講書人閱讀 52,696評(píng)論 1贊 312
城市分裂傳說
那天屋吨，我揣著相機(jī)與錄音，去河邊找鬼山宾。笑死至扰，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的资锰。我是一名探鬼主播敢课，決...
沈念sama閱讀 41,165評(píng)論 3贊 422
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長(zhǎng)吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼台妆！你這毒婦竟也來了翎猛？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 40,108評(píng)論 0贊 277
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤接剩，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后萨咳，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體懊缺，經(jīng)...
沈念sama閱讀 46,646評(píng)論 1贊 319
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 38,709評(píng)論 3贊 342
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了鹃两。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片遗座。...
茶點(diǎn)故事閱讀 40,861評(píng)論 1贊 353
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖俊扳，靈堂內(nèi)的尸體忽然破棺而出途蒋，到底是詐尸還是另有隱情，我是刑警寧澤馋记，帶...
沈念sama閱讀 36,527評(píng)論 5贊 351
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布号坡，位于F島的核電站，受9級(jí)特大地震影響梯醒，放射性物質(zhì)發(fā)生泄漏宽堆。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 42,196評(píng)論 3贊 336
男人毒藥：我在死后第九天來索命
文/蒙蒙一茸习、第九天我趴在偏房一處隱蔽的房頂上張望畜隶。院中可真熱鬧，春花似錦号胚、人聲如沸籽慢。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,698評(píng)論 0贊 25
一樁弒父案猫胁，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽箱亿。三九已至，卻和暖如春杜漠，著一層夾襖步出監(jiān)牢的瞬間极景，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 33,804評(píng)論 1贊 274
情欲美人皮
我被黑心中介騙來泰國(guó)打工驾茴，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留盼樟，地道東北人。一個(gè)月前我還...
沈念sama閱讀 49,287評(píng)論 3贊 379
代替公主和親
正文我出身青樓锈至，卻偏偏與公主長(zhǎng)得像晨缴，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子峡捡，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,860評(píng)論 2贊 361

20170908_hdu1495

推薦閱讀更多精彩內(nèi)容