#UVa:291-The House Of Santa Claus

灆洢 2014-09-30 17:03:12

利用backtracking把所有解跑一遍並輸出出來即可。

C++(0.015)

/*******************************************************/
/* UVa 291 The House Of Santa Claus                    */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2014/09/30                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

void backtracking( bool house[][6], int nowPoint, int path[], int pathsize ){
  path[pathsize] = nowPoint;

  if( pathsize == 8 ){
    for( int i = 0 ; i <= pathsize ; ++i ){
      printf( "%d", path[i] );
    }
    printf("\n");
    return;
  }

  for( int i = 1 ; i <= 5 ; ++i ){
    if( house[nowPoint][i] ){
      house[nowPoint][i] = house[i][nowPoint] = false;
      backtracking( house, i, path, pathsize + 1);
      house[nowPoint][i] = house[i][nowPoint] = true;
    }
  }
}

int main(){

  bool house[6][6] = {0};
  house[1][2] = house[2][1] = true;
  house[1][3] = house[3][1] = true;
  house[1][5] = house[5][1] = true;
  house[2][3] = house[3][2] = true;
  house[2][5] = house[5][2] = true;
  house[3][4] = house[4][3] = true;
  house[3][5] = house[5][3] = true;
  house[4][5] = house[5][4] = true;

  int path[10] = {0};
  backtracking( house, 1, path, 0 );
  return 0;
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料