UVa 10422 - Knights in FE

題目：如題目的圖示給你一個5*5的棋盤上面有12個黑騎士和12個白騎士和一個空格；

            現在要你從一個給定狀態變成目標狀態，每一可以移動一個騎士（走日字，國際象棋）；

            問多少步能走到目標狀態，超過10步輸出超過10步走到。

            目標狀態：

分析：搜索，狀態壓縮，哈希表。用一個25位的01串可以表示任意一種狀態；

           （空格全用0表示，也可全用1表示，避免當做兩種狀態）

            所以每個狀態可以用一個int類型的數據表示，然後計算出個狀態的到達關係，bfs即可；

            搜索時使用hash函數壓縮數據（頭則內存不夠）。

說明：大年三十的刷道題╮(╯▽╰)╭。

#include 
#include 
#include 
#include 
#include 
#include using namespace std;char in[5][6];
int  dxy[8][2] = {-2,-1,-2,1,2,-1,2,1,-1,-2,-1,2,1,-2,1,2};
int  jump[25][8];typedef struct _d_node
{int value;int space;int steps;
}_data_node;//hash_list_begin
typedef struct _h_node
{_data_node 	data;_h_node* 	next;
}_hash_node;
_hash_node 	_hash_list[100000];
_hash_node *_hash_head[100000];
int         _hash_size;void hash_init(void)
{_hash_size = 0;memset(_hash_head, 0 , sizeof(_hash_head));memset(_hash_list, 0 , sizeof(_hash_list));
}int hash_find(_data_node v)
{int value = v.value%100000;for (_hash_node* p = _hash_head[value] ; p ; p = p->next)if (p->data.value == v.value && p->data.space == v.space)return 1;return 0;
}void hash_add(_data_node v)
{int value = v.value%100000;_hash_list[_hash_size].data = v;_hash_list[_hash_size].next = _hash_head[value];_hash_head[value] = &_hash_list[_hash_size ++];
}
//hash_list_end//测试用输出函数 
void show(_data_node a)
{printf("%2d:%2d\n",a.space,a.steps);int temp[32],save = 0;for (int i = 0 ; i < 32 ; ++ i)temp[i] = 0;int count = 0;while (a.value) {count += temp[save ++] = a.value%2;a.value /= 2;}for (int i = 0 ; i < 25 ; ++ i) {if (a.space == i) printf(" ");else printf("%d",temp[i]);if ((i+1)%5 == 0) printf("\n");}
}_data_node Q[100000];
void bfs(_data_node s, _data_node t)
{if (s.value == t.value && s.space == t.space) {printf("Solvable in 0 move(s).\n");return;}hash_init();int move = 0,save = 0;Q[save ++] = s;hash_add(s);while (move < save) {_data_node New,now = Q[move ++];for (int k = 0 ; k < 8 ; ++ k) {if (jump[now.space][k] == -1) continue;New.steps = now.steps + 1;if (New.steps > 10) {printf("Unsolvable in less than 11 move(s).\n");return;}New.space = jump[now.space][k];New.value = now.value&((1<<25)-1-(1<0)<= 0 && x < 5 && y >= 0 && y < 5)jump[5*i+j][k] = 5*x+y;else jump[5*i+j][k] = -1;}int n;while (~scanf("%d",&n) && n) {getchar();while (n --) {for (int i = 0 ; i < 5 ; ++ i)gets(in[i]);_data_node s;s.value = s.steps = 0;for (int i = 0 ; i < 5 ; ++ i)for (int j = 0 ; j < 5 ; ++ j) if (in[i][j] != ' ')s.value += (in[i][j]-'0')<<(i*5+j);else s.space = (i*5+j);bfs(s, t);}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！