广搜——最优方案

Wikioi 1225 八数码难题

题目描述 Description

Yours和zero在研究A*启发式算法.拿到一道经典的A*问题,但是他们不会做,请你帮他们.
问题描述

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入描述 Input Description

输入初试状态，一行九个数字，空格用0表示

输出描述 Output Description

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

样例输入 Sample Input

283104765

样例输出 Sample Output

数据范围及提示 Data Size & Hint

详见试题

思路：

（康托展开+双向广搜） or ida*

代码：

①双向广搜：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<string>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<queue>
  7 #include<map>
  8 #include<algorithm>
  9 #define mx 4000000
 10 using namespace std;
 11 
 12 struct chess{
 13     int node[9];
 14     int step;
 15     int pos;
 16     bool cla;
 17 };
 18 int chart = 0,step[2][10000];
 19 map<int,int> trans[2];
 20 chess start,end;
 21 bool jud[2][mx];
 22 int m_jud[9][4] = {1,3,-1,-1,
 23                    0,4,2,-1,
 24                    1,5,-1,-1,
 25                    0,4,6,-1,
 26                    1,3,5,7,
 27                    2,4,8,-1,
 28                    3,7,-1,-1,
 29                    4,6,8,-1,
 30                    5,7,-1,-1};
 31 
 32 int getval(chess x){
 33     int res = 1,val = 0;
 34     for(int i = 1;i <= 9;i++){
 35         val += res * x.node[i-1];
 36         res *= (i+1);
 37     }
 38     return val;
 39 }
 40 void putout(chess pt){
 41     cout<<"the class:"<<pt.cla<<endl;
 42     for(int i = 1;i <= 3;i++){
 43         for(int j = 1;j <= 3;j++){
 44             cout<<pt.node[(i-1) * 3 + j - 1] <<" ";
 45         }
 46         cout<<endl;
 47     }
 48     cout<<"steps: "<<pt.step<<" , pos: "<<pt.pos<<endl;
 49 }
 50 void init(){
 51     int co,md = 1;
 52     cin>>co;
 53     for(int i = 8;i >= 0;i--){
 54         start.node[i] = (co / md)% 10;
 55         md *= 10;
 56         if(start.node[i] == 0) start.pos = i;
 57         
 58     }
 59     start.cla = 0;
 60     end.node[0] = 1;
 61     end.node[1] = 2;
 62     end.node[2] = 3;
 63     end.node[3] = 8;
 64     end.node[4] = 0;
 65     end.node[5] = 4;
 66     end.node[6] = 7;
 67     end.node[7] = 6;
 68     end.node[8] = 5;
 69     end.step = start.step = 0;
 70     end.pos = 4;
 71     end.cla = 1;
 72 }
 73 void bfs(){
 74     queue<chess> now,then;
 75     now.push(start);
 76     now.push(end);
 77     chess test,h;
 78     int p,code;
 79     while(!now.empty()){
 80         h = now.front();
 81         p = h.pos;
 82         code = getval(h);
 83         trans[h.cla][code] = chart;
 84         step[h.cla][chart] = h.step;
 85         chart++;
 86         jud[h.cla][code] = 1;
 87         for(int i = 0,j = m_jud[p][i];j != -1 && i <= 3;i++,j = m_jud[p][i]){
 88             test = h;
 89             test.step++;
 90             swap(test.node[p],test.node[j]);
 91             code = getval(test);
 92             //if(jud[test.cla][code]) continue;
 93             test.pos = j;
 94             trans[test.cla][code] = chart;
 95             step[test.cla][chart] = test.step;
 96             chart++;
 97             if(jud[!test.cla][code]){
 98                 cout<<step[0][trans[0][code]] + step[1][trans[1][code]]<<endl;
 99                 return;
100             }
101             if(!jud[test.cla][code]){
102                 now.push(test);
103                 jud[test.cla][code] = 1;
104             }
105             
106         }
107         now.pop();
108     }
109 }
110 int main(){
111 
112     init();    
113     bfs();
114     return 0;
115 }

View Code

②IDA*：

  1 #include <iostream>
  2 #include <cmath>
  3 #include <cstdlib>
  4 #include <cstdio>
  5 #include <cstring>
  6 using namespace std;
  7 const unsigned int M = 1001;
  8 int dir[4][2] = {
  9     1, 0, // Down
 10     -1, 0, // Up
 11     0,-1, // Left
 12     0, 1 // Right
 13 };
 14 typedef struct STATUS{
 15     int arr[3][3];
 16     int r,c;
 17 }STATUS;
 18 char dirCode[] = {"dulr"};
 19 char rDirCode[] = {"udrl"};
 20 char path[M]; // 最优解
 21 STATUS begin, end = { 1,2,3,4,5,6,7,8,0,2,2 }; // 起始和终止状态
 22 int maxDepth = 0; // 深度边界
 23 int diff(const STATUS &cur) // 启发函数
 24 {
 25     int i,j,k,m,ans=0;
 26     for(i=0;i<=2;i++)
 27         for(j=0;j<=2;j++)
 28         {
 29             if(cur.arr[i][j] != 0)
 30             {
 31                 for(k=0;k<=2;k++)
 32                     for(m=0;m<=2;m++)
 33                     {
 34                         if(cur.arr[i][j] == end.arr[k][m])
 35                         {
 36                             ans+=abs(i-k)+abs(j-m);
 37                             break;
 38                         }
 39                     }
 40             }
 41         }
 42     return ans;
 43 }
 44 bool dfs(STATUS &cur, int depth, int h, char preDir)
 45 {
 46     if(memcmp(&cur, &end, sizeof(STATUS)) == 0 )
 47     { // OK找到解了:)
 48         path[depth] = '/0';
 49         return true;
 50     }
 51     if( depth + h > maxDepth ) return false; // 剪枝
 52     STATUS nxt; // 下一状态
 53     for(int i=0; i<4; i++)
 54     {
 55         if(dirCode[i]==preDir) continue; // 回到上次状态,剪枝
 56         nxt = cur;
 57         nxt.r = cur.r + dir[i][0];
 58         nxt.c = cur.c + dir[i][1];
 59         if( !( nxt.r >= 0 && nxt.r < 3 && nxt.c >= 0 && nxt.c < 3 ) )
 60             continue;
 61         int nxth = h;
 62         int preLen,Len,desNum=cur.arr[nxt.r][nxt.c],desR=(desNum-1)/3,desC=(desNum-1)%3;
 63         preLen=abs(nxt.r-desR)+abs(nxt.c-desC);
 64         Len=abs(cur.r-desR)+abs(cur.c-desC);
 65         nxth = h - preLen + Len;
 66         swap(nxt.arr[cur.r][cur.c], nxt.arr[nxt.r][nxt.c]);
 67         path[depth] = dirCode[i];
 68         if(dfs(nxt, depth + 1, nxth, rDirCode[i]))
 69             return true;
 70     }
 71     return false;
 72 }
 73 int IDAstar()
 74 {
 75     int nh = diff(begin);
 76     maxDepth = nh;
 77     while (!dfs(begin, 0, nh, '/0'))
 78         maxDepth++;
 79     return maxDepth;
 80 }
 81 void Input()
 82 {
 83     char ch;
 84     int i, j;
 85     for(i=0; i < 3; i++){
 86         for(j=0; j < 3; j++){
 87             do{
 88                 scanf("%c", &ch);
 89             }
 90             while( !( ( ch >= '1' && ch <= '8' ) || ( ch == 'x' ) ) ) 
 91                 ;
 92             if( ch == 'x' ) {
 93                 begin.arr[i][j] = 0;
 94                 begin.r = i;
 95                 begin.c = j;
 96             }
 97             else
 98                 begin.arr[i][j] = ch - '0';
 99         }
100     }
101 }
102 bool IsSolvable(const STATUS &cur)
103 {
104     int i, j, k=0, s = 0;
105     int a[8];
106     for(i=0; i < 3; i++){
107         for(j=0; j < 3; j++){
108             if(cur.arr[i][j]==0) continue;
109             a[k++] = cur.arr[i][j];
110         }
111     }
112     for(i=0; i < 8; i++){
113         for(j=i+1; j < 8; j++){
114             if(a[j] < a[i])
115                 s++;
116         }
117     }
118     return (s%2 == 0);
119 }
120 int main()
121 {
122     Input();
123     if(IsSolvable(begin)){
124         IDAstar();
125         printf("%s/n", path);
126     }
127     else
128         printf("unsolvable/n");
129     return 0;
130 }

View Code

Wikioi 2449 骑士精神

题目描述 Description

在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士，且有一个空位。在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空位上。

给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘：

为了体现出骑士精神，他们必须以最少的步数完成任务。

输入描述 Input Description

第一行有一个正整数T(T<=10)，表示一共有N组数据。接下来有T个5×5的矩阵，0表示白色骑士，1表示黑色骑士，*表示空位。两组数据之间没有空行。

输出描述 Output Description

对于每组数据都输出一行。如果能在15步以内（包括15步）到达目标状态，则输出步数，否则输出－1。

样例输入 Sample Input

01*11

110*1

样例输出 Sample Output

-1

数据范围及提示 Data Size & Hint

见题面

思路：

IDA*

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<string>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<algorithm>
 7 #define mx 5
 8 using namespace std;
 9 struct Board{
10     int board[mx][mx];
11     int bx,by;
12     
13 };
14 int ans[mx][mx] = {{1,1,1,1,1},
15                    {2,1,1,1,1},
16                    {2,2,0,1,1},
17                    {2,2,2,2,1},
18                    {2,2,2,2,2}};
19 int dx[8] = {1,2,2,1,-1,-2,-2,-1};
20 int dy[8] = {2,1,-1,-2,-2,-1,1,2};
21 int d,id,bx,by;
22 Board start;
23 void input(){
24     char tmp;
25     for(int i = 0;i < 5;i++){
26         for(int j = 0;j < 5;j++){
27             cin>>tmp;
28             if(tmp == '*'){
29                 start.board[i][j] = 0;
30                 by = i;
31                 bx = j;
32             }
33             if(tmp == '1') start.board[i][j] = 1;
34             if(tmp == '0') start.board[i][j] = 2;
35         }
36     }
37 }
38 int h(Board a){
39     int ret = 0;
40     for(int i = 0;i < 5;i++){
41         for(int j = 0;j < 5;j++){
42             ret += (ans[i][j] != a.board[i][j]);
43         }
44     }
45     return ret;
46 }
47 bool idastar(int step,int maxdeep){
48     if(step > maxdeep) return false;
49     int g = h(start),bx,by;
50     if(!g) return true;
51     if(g + step - 1> maxdeep) return false;
52     for(int i = 0;i < 5;i++){
53         for(int j = 0;j < 5;j++){
54             if(start.board[i][j] == 0){
55                 bx = j;
56                 by = i;
57             }
58         }
59     }
60     for(int i = 0;i < 8;i++){
61         if(bx + dx[i] < 0 || bx + dx[i] >= mx || by + dy[i] < 0 || by + dy[i] >= mx) continue;
62         swap(start.board[by + dy[i]][bx + dx[i]],start.board[by][bx]);
63         if(idastar(step+1,maxdeep))return true;
64         swap(start.board[by + dy[i]][bx + dx[i]],start.board[by][bx]);
65     }
66     return false;
67 }
68 int main(){
69     int T;
70     cin>>T;
71     while(T--){
72     input();
73     for(id = 0;id <= 15;id++){
74         if(idastar(0,id)){
75             cout<<id<<endl;
76             break;
77         }
78     }
79     if(id > 15) cout<<-1<<endl;
80 }
81     return 0;
82 }

View Code

Wikioi 1226 倒水问题

题目描述 Description

有两个无刻度标志的水壶，分别可装 x 升和 y 升（ x,y 为整数且均不大于 100 ）的水。设另有一水缸，可用来向水壶灌水或接从水壶中倒出的水，两水壶间，水也可以相互倾倒。已知 x 升壶为空壶， y 升壶为空壶。问如何通过倒水或灌水操作，用最少步数能在x或y升的壶中量出 z （ z ≤ 100 ）升的水来。

输入描述 Input Description

一行，三个数据，分别表示 x,y 和 z;

输出描述 Output Description

一行，输出最小步数 ,如果无法达到目标，则输出"impossible"

样例输入 Sample Input

3 22 1

样例输出 Sample Output

思路：

普通广搜

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<string>
 4 #include<cstring>
 5 #include<algorithm>
 6 #define maxn 100000
 7 using namespace std;
 8 struct sta{
 9     int x;
10     int y; 
11     int step;
12     int frm;
13 };
14 int mx,my,z,j[101][101],solved = 0;
15 sta temp;
16 void input(){
17     cin>>mx>>my>>z;
18     temp.x = temp.y = temp.step = 0;
19     temp.frm = -1;
20 }
21 sta expand(sta a,int sign){
22     if(sign == 0) a.x = 0;
23     if(sign == 1) a.y = 0;
24     if(sign == 2) a.x = mx;
25     if(sign == 3) a.y = my;
26     if(sign == 4){
27         int d;
28         if(mx - a.x < a.y) d = mx - a.x;
29         else d = a.y;
30         a.y -= d;
31         a.x += d;
32     }
33     if(sign == 5){
34         int d;
35         if(my - a.y < a.x) d = my - a.y;
36         else d = a.x;
37         a.y += d;
38         a.x -= d;
39     }
40     a.frm = sign;
41     a.step++;
42     if(j[a.x][a.y]) a.step = -1;
43     j[a.x][a.y] = 1;
44     return a;
45 }
46 void bfs(){
47     sta q[maxn];
48     int h = 0,t = 1;
49     q[h] = temp;
50     while(h != t){
51         if(q[h%maxn].x == z || q[h%maxn].y == z) {
52             cout<<q[h%maxn].step<<endl;
53             solved = 1;
54             break;
55         }
56         for(int i = 0;i <= 5;i++){
57            if(i == 0 && (q[h%maxn].x == 0 ||q[h%maxn].frm == 2)) continue;
58            if(i == 1 && (q[h%maxn].y == 0 ||q[h%maxn].frm == 3)) continue;
59            if(i == 2 && (q[h%maxn].x == mx ||q[h%maxn].frm == 0)) continue;
60            if(i == 3 && (q[h%maxn].y == my ||q[h%maxn].frm == 1)) continue;
61            if(i == 4 && (q[h%maxn].y <= 0 || q[h%maxn].x >= mx || q[h%maxn].frm == 5)) continue;
62            if(i == 5 && (q[h%maxn].x <= 0 || q[h%maxn].y >= my || q[h%maxn].frm == 4)) continue;
63            temp = expand(q[h%maxn],i);
64            
65            if(temp.step != -1) {
66                t++;
67                    q[t%maxn] = temp;
68                       
69            }
70         }
71         h++;
72     }
73 }
74 int main(){
75     input();
76     if(z > mx || z > my || !mx || !my || (mx == my && mx != z)){
77         cout<<"impossible"<<endl;
78         return 0;
79     }
80     bfs();
81     if(!solved)    cout<<"impossible"<<endl;
82     return 0;
83 }

View Code