sicily_1151 魔板

題目

見sicily_1150 簡單魔板
僅僅是最大步數(shù)可以超過10.

思路

直接剪枝bfs酸员，然而很不幸地樓主一直MLE……
使用康托展開公式來檢查一個節(jié)點是否已經(jīng)遍歷過。因為能夠?qū)個無重復(fù)元素的排列映射到剛好n!個數(shù)讳嘱，所以可以大大地節(jié)省內(nèi)存幔嗦。

代碼

// Copyright (c) 2015 HuangJunjie@SYSU(SNO:13331087). All Rights Reserved.
// 1151 魔板: http://soj.sysu.edu.cn/1151
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>

using namespace std;

struct Node {
  int state;
  string opt;
};

bool isvisited[40320] = { 0 };
int factor[8] = { 1, 1, 2, 6, 24, 120, 720, 5040 };

Node doA(const Node& node);
Node doB(const Node& node);
Node doC(const Node& node);

int contor(Node current);

int main() {
  int max_steps;
  Node aim;

  Node start;
  start.state = 12348765;
  start.opt = "";

  while (scanf("%d", &max_steps) != EOF && max_steps != -1) {
    int digit;
    aim.state = 0;
    for (int i = 0; i < 8; i++) {
      scanf("%d", &digit);
      aim.state *= 10;
      aim.state += digit;
    }

    memset(isvisited, 0, sizeof(isvisited));
    queue<Node> que;
    que.push(start);
    while (!que.empty()) {
      Node current = que.front();
      que.pop();
      if (isvisited[contor(current)] == true) continue;
      else
        isvisited[contor(current)] = true;

      if (current.opt.size() > max_steps) {
        printf("-1\n");
        break;
      }

      if (contor(current) == contor(aim)) {
        printf("%d %s\n", current.opt.size(), current.opt.c_str());
        break;
      }

      Node Anext = doA(current);
      // if (isvisited[contor(Anext)] == false)
        que.push(Anext);
      Node Bnext = doB(current);
      // if (isvisited[contor(Anext)] == false)
        que.push(Bnext);
      Node Cnext = doC(current);
      // if (isvisited[contor(Anext)] == false)
        que.push(Cnext);
    }
  }

  return 0;
}

Node doA(const Node& node) {
  Node Anext;
  Anext.state = node.state % 10000 * 10000 + node.state / 10000;
  Anext.opt = node.opt + 'A';

  return Anext;
}

Node doB(const Node& node) {
  Node Bnext;
  int up = node.state / 10000;
  int down = node.state % 10000;
  Bnext.state = (up / 10 + up % 10 * 1000) * 10000 + (down / 10 + down % 10 * 1000);
  Bnext.opt = node.opt + 'B';

  return Bnext;
}

Node doC(const Node& node) {
  Node Cnext;
  int fact = 10000000;
  int temp[8];
  for (int i = 0; i < 8; i++) {
    temp[i] = (node.state / fact) % 10;
    fact /= 10;
  }

  Cnext.state = (temp[0] * 1000 + temp[5] * 100 + temp[1] * 10 + temp[3]) * 10000 +
    (temp[4] * 1000 + temp[6] * 100 + temp[2] * 10 + temp[7]);
  Cnext.opt = node.opt + 'C';

  return Cnext;
}

int contor(Node current) {
  int fact = 10000000;
  int temp[8];
  for (int i = 0; i < 8; i++) {
    temp[i] = (current.state / fact) % 10;
    fact /= 10;
  }

  int sum = 0;
  for (int i = 0; i < 8; i++) {
    int count = 0;
    for (int j = i + 1; j < 8; j++) {
      if (temp[i] > temp[j]) count++;
    }
    sum += count*factor[7 - i];
  }


  return sum;
}

優(yōu)化

將已經(jīng)遍歷過的節(jié)點的狀態(tài)存起來即可，算是小小的優(yōu)化吧沥潭。

// Copyright (c) 2015 HuangJunjie@SYSU(SNO:13331087). All Rights Reserved.
// 1151 魔板: http://soj.sysu.edu.cn/1151
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>

using namespace std;

struct Node {
  int state;
  string opt;
};

bool isvisited[40320] = { 0 };
string opts[40320];         // operation records
int factor[8] = { 1, 1, 2, 6, 24, 120, 720, 5040 };

Node doA(const Node& node);
Node doB(const Node& node);
Node doC(const Node& node);

int contor(Node current);

int main() {
  int max_steps;
  Node aim;

  Node start;
  start.state = 12348765;
  start.opt = "";

  while (scanf("%d", &max_steps) != EOF && max_steps != -1) {
    int digit;
    aim.state = 0;
    for (int i = 0; i < 8; i++) {
      scanf("%d", &digit);
      aim.state *= 10;
      aim.state += digit;
    }

    if (opts[contor(aim)] != "") {
      printf("%d %s\n", opts[contor(aim)].size(), opts[contor(aim)].c_str());
      continue;
    }

    memset(isvisited, 0, sizeof(isvisited));
    queue<Node> que;
    que.push(start);
    while (!que.empty()) {
      Node current = que.front();
      que.pop();
      if (isvisited[contor(current)] == true) {
        continue;
      } else {
        isvisited[contor(current)] = true;
        
        // stores the operation path.
        if (opts[contor(current)] == "")
          opts[contor(current)] = current.opt;
      }
      if (current.opt.size() > max_steps) {
        printf("-1\n");
        break;
      }

      if (contor(current) == contor(aim)) {
        printf("%d %s\n", current.opt.size(), current.opt.c_str());
        break;
      }

      Node Anext = doA(current);
      que.push(Anext);
      Node Bnext = doB(current);
      que.push(Bnext);
      Node Cnext = doC(current);
      que.push(Cnext);
    }
  }

  return 0;
}

Node doA(const Node& node) {
  Node Anext;
  Anext.state = node.state % 10000 * 10000 + node.state / 10000;
  Anext.opt = node.opt + 'A';

  return Anext;
}

Node doB(const Node& node) {
  Node Bnext;
  int up = node.state / 10000;
  int down = node.state % 10000;
  Bnext.state = (up / 10 + up % 10 * 1000) * 10000 + (down / 10 + down % 10 * 1000);
  Bnext.opt = node.opt + 'B';

  return Bnext;
}

Node doC(const Node& node) {
  Node Cnext;
  int fact = 10000000;
  int temp[8];
  for (int i = 0; i < 8; i++) {
    temp[i] = (node.state / fact) % 10;
    fact /= 10;
  }

  Cnext.state = (temp[0] * 1000 + temp[5] * 100 + temp[1] * 10 + temp[3]) * 10000 +
    (temp[4] * 1000 + temp[6] * 100 + temp[2] * 10 + temp[7]);
  Cnext.opt = node.opt + 'C';

  return Cnext;
}

int contor(Node current) {
  int fact = 10000000;
  int temp[8];
  for (int i = 0; i < 8; i++) {
    temp[i] = (current.state / fact) % 10;
    fact /= 10;
  }

  int sum = 0;
  for (int i = 0; i < 8; i++) {
    int count = 0;
    for (int j = i + 1; j < 8; j++) {
      if (temp[i] > temp[j]) count++;
    }
    sum += count*factor[7 - i];
  }

  return sum;
}

隨機樣例生成

// Copyright (c) 2015 HuangJunjie@SYSU(SNO:13331087). All Rights Reserved.
#define ALPHA_SIZE 26
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <ctime>

#include <cstdio>
#include <string>
#include <queue>
#include <vector>

using namespace std;

struct Node {
  int state;
  string opt;
} start;

bool isvisited[40320] = { 0 };
string opts[40320];         // operation records
int factor[8] = { 1, 1, 2, 6, 24, 120, 720, 5040 };

Node doA(const Node& node);
Node doB(const Node& node);
Node doC(const Node& node);

int contor(Node current);

fstream testcase;
fstream answer;

void init();
void makeTestCase(int cases);
void build();
void bfs(Node aim);

Node recontor(int i);

int main() {
  init();

  for (int cases = 10; cases < 10000; cases *= 10) {
    makeTestCase(cases);
  }
  for (int cases = 50; cases < 50000; cases *= 10) {
    makeTestCase(cases);
  }

  return 0;
}

void init() {
  srand(time(NULL));
  start.state = 12348765;
  start.opt = "";

  build();
}

void build() {
  for (int i = 0; i < 40320; i++) {
    if (opts[i] == "") {
      Node aim = recontor(i);
      bfs(aim);
    }
  }
}

void bfs(Node aim) {
  memset(isvisited, 0, sizeof(isvisited));
  queue<Node> que;
  que.push(start);
  while (!que.empty()) {
    Node current = que.front();
    que.pop();
    if (isvisited[contor(current)] == true) {
      continue;
    } else {
      isvisited[contor(current)] = true;

      // stores the operation path.
      if (opts[contor(current)] == "")
        opts[contor(current)] = current.opt;
    }

    if (contor(current) == contor(aim)) {
      return;
    }

    Node Anext = doA(current);
    que.push(Anext);
    Node Bnext = doB(current);
    que.push(Bnext);
    Node Cnext = doC(current);
    que.push(Cnext);
  }
}

void makeTestCase(int cases) {
  char buf[5];
  sprintf(buf, "%d", cases);
  string cases_str = buf;
  string inputname = "input" + cases_str + ".txt";
  string answername = "answer" + cases_str + ".txt";
  testcase.open(inputname, ios::out);
  answer.open(answername, ios::out);

  for (int i = 0; i < cases; i++) {
    int steps = rand() % cases;

    testcase << steps << endl;
    int key = rand() % 40320;

    Node test = recontor(key);

    for (int factor = 10000000; factor; factor /= 10) {
      if (factor != 10000000 && factor != 1000) testcase << " ";
      if (factor == 1000) testcase << endl;
      testcase << test.state / factor;
      test.state %= factor;
    }
    testcase << endl;

    answer << opts[key].size() << " " << opts[key] << endl;
  }
  testcase << -1 << endl;

  testcase.close();
  answer.close();
}

Node doA(const Node& node) {
  Node Anext;
  Anext.state = node.state % 10000 * 10000 + node.state / 10000;
  Anext.opt = node.opt + 'A';

  return Anext;
}

Node doB(const Node& node) {
  Node Bnext;
  int up = node.state / 10000;
  int down = node.state % 10000;
  Bnext.state = (up / 10 + up % 10 * 1000) * 10000 + (down / 10 + down % 10 * 1000);
  Bnext.opt = node.opt + 'B';

  return Bnext;
}

Node doC(const Node& node) {
  Node Cnext;
  int fact = 10000000;
  int temp[8];
  for (int i = 0; i < 8; i++) {
    temp[i] = (node.state / fact) % 10;
    fact /= 10;
  }

  Cnext.state = (temp[0] * 1000 + temp[5] * 100 + temp[1] * 10 + temp[3]) * 10000 +
    (temp[4] * 1000 + temp[6] * 100 + temp[2] * 10 + temp[7]);
  Cnext.opt = node.opt + 'C';

  return Cnext;
}

int contor(Node current) {
  int fact = 10000000;
  int temp[8];
  for (int i = 0; i < 8; i++) {
    temp[i] = (current.state / fact) % 10;
    fact /= 10;
  }

  int sum = 0;
  for (int i = 0; i < 8; i++) {
    int count = 0;
    for (int j = i + 1; j < 8; j++) {
      if (temp[i] > temp[j]) count++;
    }
    sum += count*factor[7 - i];
  }

  return sum;
}

Node recontor(int key) {
  Node result;
  result.state = 0;
  bool num[8] = { 0 };
  for (int i = 7; i >= 0; i--) {
    int count = -1;
    int remain = key / factor[i];
    key %= factor[i];
    for (int j = 0; j < 8; j++) {
      if (num[j] == false) count++;
      if (count == remain) {
        num[j] = true;
        result.state *= 10;
        result.state += j + 1;
        break;
      }
    }
  }

  return result;
}

最后編輯于：2017.11.27 04:06:38

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

人面猴
序言：七十年代末邀泉，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子钝鸽，更是在濱河造成了極大的恐慌汇恤，老刑警劉巖，帶你破解...
沈念sama閱讀 216,997評論 6贊 502
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件拔恰，死亡現(xiàn)場離奇詭異因谎，居然都是意外死亡，警方通過查閱死者的電腦和手機颜懊，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,603評論 3贊 392
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門财岔，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人饭冬，你說我怎么就攤上這事【窘祝” “怎么了昌抠？”我有些...
開封第一講書人閱讀 163,359評論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長鲁僚。經(jīng)常有香客問我炊苫，道長，這世上最難降的妖魔是什么冰沙？我笑而不...
開封第一講書人閱讀 58,309評論 1贊 292
?港島之戀（遺憾婚禮）
正文為了忘掉前任侨艾，我火速辦了婚禮，結(jié)果婚禮上拓挥，老公的妹妹穿的比我還像新娘唠梨。我一直安慰自己，他們只是感情好侥啤，可當我...
茶點故事閱讀 67,346評論 6贊 390
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布当叭。她就那樣靜靜地躺著，像睡著了一般盖灸。火紅的嫁衣襯著肌膚如雪蚁鳖。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,258評論 1贊 300
城市分裂傳說
那天赁炎，我揣著相機與錄音醉箕，去河邊找鬼。笑死，一個胖子當著我的面吹牛讥裤，可吹牛的內(nèi)容都是我干的放棒。我是一名探鬼主播，決...
沈念sama閱讀 40,122評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼坞琴，長吁一口氣：“原來是場噩夢啊……” “哼哨查！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起剧辐，我...
開封第一講書人閱讀 38,970評論 0贊 275
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤寒亥，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后荧关，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體溉奕，經(jīng)...
沈念sama閱讀 45,403評論 1贊 313
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,596評論 3贊 334
?白月光啟示錄
正文我和宋清朗相戀三年忍啤，在試婚紗的時候發(fā)現(xiàn)自己被綠了加勤。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點故事閱讀 39,769評論 1贊 348
活死人
序言：一個原本活蹦亂跳的男人離奇死亡同波，死狀恐怖鳄梅，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情未檩，我是刑警寧澤戴尸，帶...
沈念sama閱讀 35,464評論 5贊 344
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站冤狡，受9級特大地震影響孙蒙，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜悲雳，卻給世界環(huán)境...
茶點故事閱讀 41,075評論 3贊 327
男人毒藥：我在死后第九天來索命
文/蒙蒙一挎峦、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧合瓢，春花似錦坦胶、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,705評論 0贊 22
一樁弒父案迁央，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至滥崩，卻和暖如春岖圈，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背钙皮。一陣腳步聲響...
開封第一講書人閱讀 32,848評論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工蜂科，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留顽决，地道東北人。一個月前我還...
沈念sama閱讀 47,831評論 2贊 370
代替公主和親
正文我出身青樓导匣，卻偏偏與公主長得像才菠，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子贡定，可洞房花燭夜當晚...
茶點故事閱讀 44,678評論 2贊 354

sicily_1151 魔板

題目

思路

代碼

優(yōu)化

隨機樣例生成

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