11163 - Jaguar King

[tamim1382csedu19]

How do I store individual state ? For 15-puzzle problem , It can be done by a ull, as each number is less than 15 , so 4 bit *16 = 64 bit. but here it is 40 numbers. So how Do I store the states to prevent cycling in the dfs for IDA* ?
And here is my code , I am getting TLE , http://ideone.com/gVTBMf How do I improvve my algorithm?

[Farsan]

WA.Need some test cases.

Code: Select all

#include <bits/stdc++.h>

using namespace std;

int manh[45][45],grid[45],n,bound;

int man()
{
    int r1,c1,r2,c2,i,j;
    for(i=1;i<=41;i++)
    {
        r1=(i-1)/4;
        r1++;
        c1=i%4;
        if(c1==0)
        c1=4;
        for(j=1;j<=41;j++)
        {
            r2=(j-1)/4;
            r2++;
            c2=j%4;
            if(c2==0)
            c2=4;
            manh[i][j]=abs(r1-r2)+abs(c1-c2);
        }
    }
    return 0;
}

int h()
{
    int i,j,k=0;
    for(i=1;i<=n;i++)
    {
        if(grid[i]!=1)
        k=k+manh[i][grid[i]];
    }
    return k;
}

bool done;


int solve(int g_val,int h_val,int king_pos,int mv)
{
    int f_val=g_val+h_val;
    if(h_val==0)
    {
        done=true;
        return f_val;
    }
    if(f_val>bound)
    {
        return f_val;
    }
    int mx=100000000,k,v;
    //(i+1), (i+3), (i+4), (i-4)
    if(king_pos%4==1)
    {
        if(mv!=-1&&king_pos+1<=n)
        {
            k=h_val-manh[grid[king_pos+1]][king_pos+1];
            swap(grid[king_pos],grid[king_pos+1]);
            k=k+manh[grid[king_pos]][king_pos];
            v=solve(g_val+1,k,king_pos+1,1);
            mx=min(mx,v);
            swap(grid[king_pos],grid[king_pos+1]);
        }
        if(mv!=-3&&king_pos+3<=n)
        {
            k=h_val-manh[grid[king_pos+3]][king_pos+3];
            swap(grid[king_pos],grid[king_pos+3]);
            k=k+manh[grid[king_pos]][king_pos];
            v=solve(g_val+1,k,king_pos+3,3);
            mx=min(mx,v);
            swap(grid[king_pos],grid[king_pos+3]);
        }
        if(mv!=-4&&king_pos+4<=n)
        {
            k=h_val-manh[grid[king_pos+4]][king_pos+4];
            swap(grid[king_pos],grid[king_pos+4]);
            k=k+manh[grid[king_pos]][king_pos];
            v=solve(g_val+1,k,king_pos+4,4);
            mx=min(mx,v);
            swap(grid[king_pos],grid[king_pos+4]);
        }
        if(mv!=4&&king_pos-4>0)
        {
            k=h_val-manh[grid[king_pos-4]][king_pos-4];
            swap(grid[king_pos],grid[king_pos-4]);
            k=k+manh[grid[king_pos]][king_pos];
            v=solve(g_val+1,k,king_pos-4,-4);
            mx=min(mx,v);
            swap(grid[king_pos],grid[king_pos-4]);
        }
    }
    //(i+1), (i-1), (i+4), (i-4)
    if(king_pos%4==2||king_pos%4==3)
    {
        if(mv!=-1&&king_pos+1<=n)
        {
            k=h_val-manh[grid[king_pos+1]][king_pos+1];
            swap(grid[king_pos],grid[king_pos+1]);
            k=k+manh[grid[king_pos]][king_pos];
            v=solve(g_val+1,k,king_pos+1,1);
            mx=min(mx,v);
            swap(grid[king_pos],grid[king_pos+1]);
        }
        if(mv!=1&&king_pos-1>0)
        {
            k=h_val-manh[grid[king_pos-1]][king_pos-1];
            swap(grid[king_pos],grid[king_pos-1]);
            k=k+manh[grid[king_pos]][king_pos];
            v=solve(g_val+1,k,king_pos-1,-1);
            mx=min(mx,v);
            swap(grid[king_pos],grid[king_pos-1]);
        }
        if(mv!=-4&&king_pos+4<=n)
        {
            k=h_val-manh[grid[king_pos+4]][king_pos+4];
            swap(grid[king_pos],grid[king_pos+4]);
            k=k+manh[grid[king_pos]][king_pos];
            v=solve(g_val+1,k,king_pos+4,4);
            mx=min(mx,v);
            swap(grid[king_pos],grid[king_pos+4]);
        }
        if(mv!=4&&king_pos-4>0)
        {
            k=h_val-manh[grid[king_pos-4]][king_pos-4];
            swap(grid[king_pos],grid[king_pos-4]);
            k=k+manh[grid[king_pos]][king_pos];
            v=solve(g_val+1,k,king_pos-4,-4);
            mx=min(mx,v);
            swap(grid[king_pos],grid[king_pos-4]);
        }
    }
    //(i-3), (i-1), (i+4), (i-4)
    if(king_pos%4==0)
    {
        if(mv!=3&&king_pos-3>0)
        {
            k=h_val-manh[grid[king_pos-3]][king_pos-3];
            swap(grid[king_pos],grid[king_pos-3]);
            k=k+manh[grid[king_pos]][king_pos];
            v=solve(g_val+1,k,king_pos-3,-3);
            mx=min(mx,v);
            swap(grid[king_pos],grid[king_pos-3]);
        }

        if(mv!=1&&king_pos-1>0)
        {
            k=h_val-manh[grid[king_pos-1]][king_pos-1];
            swap(grid[king_pos],grid[king_pos-1]);
            k=k+manh[grid[king_pos]][king_pos];
            v=solve(g_val+1,k,king_pos-1,-1);
            mx=min(mx,v);
            swap(grid[king_pos],grid[king_pos-1]);
        }
        if(mv!=-4&&king_pos+4<=n)
        {
            k=h_val-manh[grid[king_pos+4]][king_pos+4];
            swap(grid[king_pos],grid[king_pos+4]);
            k=k+manh[grid[king_pos]][king_pos];
            v=solve(g_val+1,k,king_pos+4,4);
            mx=min(mx,v);
            swap(grid[king_pos],grid[king_pos+4]);
        }
        if(mv!=4&&king_pos-4>0)
        {
            k=h_val-manh[grid[king_pos-4]][king_pos-4];
            swap(grid[king_pos],grid[king_pos-4]);
            k=k+manh[grid[king_pos]][king_pos];
            v=solve(g_val+1,k,king_pos-4,-4);
            mx=min(mx,v);
            swap(grid[king_pos],grid[king_pos-4]);
        }
    }
    return mx;
}


int ida(int king_pos)
{
    bound=h();
    done=false;
    int m=bound;
    while(!done)
    {
        bound=solve(0,m,king_pos,10);
    }
    return bound;
}

int main()
{
    int cs=0,i,j;
    man();
    while(cin>>n&&n)
    {
        for(i=1;i<=n;i++)
        {
            cin>>grid[i];
            if(grid[i]==1)
                j=i;

        }
        cs++;
        cout<<"Set "<<cs<<":\n";
        cout<<ida(j)<<endl;
    }

    return 0;
}

[brianfry713]

Input:

Code: Select all

40
8 2 7 3 4 6 11 5 9 14 10 12 13 15 16 20 18 22 19 17 21 26 23 24 25 30 27 28 29 31 1 32 37 34 35 39 40 38 33 36
40
4 3 7 8 5 11 12 2 10 9 16 6 20 13 15 24 1 14 18 17 23 21 19 25 26 22 30 28 29 31 27 32 33 34 35 36 37 38 39 40
40
1 2 3 8 4 6 7 5 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
4
1 2 3 4
36
4 2 7 3 5 1 6 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
32
2 6 3 4 5 10 1 7 9 14 11 8 16 13 15 12 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
24
5 2 3 8 4 11 12 6 1 9 7 13 14 15 10 16 17 18 19 20 21 22 23 24
40
4 5 3 7 9 2 6 8 10 11 15 12 13 18 16 20 17 19 14 24 21 22 23 1 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
36
4 2 3 8 5 10 7 12 1 9 11 6 13 14 15 20 17 18 16 19 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
20
5 6 4 2 12 8 7 3 1 10 9 16 13 14 11 15 17 18 19 20
28
3 6 12 10 5 7 2 8 16 9 11 4 13 1 17 14 21 18 15 19 25 22 23 20 28 26 27 24
20
5 1 2 4 9 10 3 7 16 13 6 12 11 8 15 14 17 18 19 20
20
4 8 2 1 5 6 7 3 9 10 11 12 13 14 15 16 17 18 19 20
16
2 3 1 4 9 5 7 6 16 12 11 8 14 10 15 13
8
7 6 5 4 8 3 1 2
40
5 6 2 3 8 12 7 4 17 10 11 9 14 16 18 1 20 13 15 19 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
28
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
4
4 2 1 3
32
4 2 3 8 5 11 10 7 9 6 15 12 16 13 14 20 1 18 19 24 17 22 23 28 21 25 26 27 29 30 31 32
40
5 2 3 4 9 6 7 8 10 14 12 15 24 18 11 13 19 20 23 16 17 22 27 21 25 30 26 28 29 31 32 36 33 34 35 1 37 38 39 40
16
2 3 7 4 5 6 8 1 9 10 11 12 13 14 15 16
8
3 4 7 2 1 6 8 5
20
5 2 3 4 10 13 7 8 12 9 11 16 6 18 1 15 17 19 14 20
32
5 2 3 4 9 6 11 8 7 10 12 16 1 14 15 20 13 18 24 23 17 22 19 21 25 26 27 28 29 30 31 32
32
3 6 1 2 7 8 4 11 9 10 12 5 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
40
5 2 3 4 9 6 7 8 14 13 11 12 17 10 15 16 1 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
8
4 2 3 7 5 8 1 6
16
5 2 3 4 8 6 7 12 9 10 11 1 13 14 15 16
8
8 5 1 2 6 3 7 4
36
3 5 8 4 9 2 7 6 10 14 11 12 13 15 19 16 1 21 20 22 28 24 23 17 33 18 26 32 30 25 27 31 36 34 35 29
8
5 1 2 3 8 7 4 6
8
6 2 3 8 5 7 1 4
16
16 5 3 12 6 2 7 15 4 10 13 8 9 11 1 14
40
4 2 3 8 5 6 7 12 9 1 11 16 13 10 14 15 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
4
4 2 3 1
16
6 3 2 4 5 7 11 8 10 14 12 9 13 1 15 16
24
11 5 2 4 8 9 3 6 12 1 10 16 18 14 15 13 7 17 19 20 24 21 23 22
40
5 2 3 4 8 6 7 12 21 10 9 13 1 18 11 14 22 19 15 16 27 26 17 28 24 25 23 30 29 31 35 20 33 34 36 32 37 38 39 40
28
8 5 2 4 7 6 11 3 1 9 10 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
40
2 8 14 7 5 10 6 4 9 11 15 3 13 19 16 12 18 1 17 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
8
5 2 3 4 6 7 8 1
40
2 5 6 3 9 8 7 4 10 11 16 13 1 18 14 24 15 20 22 12 17 21 19 23 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
24
5 6 2 4 9 1 3 7 18 12 15 8 13 16 10 11 20 17 19 14 21 22 23 24
36
3 1 4 5 10 2 7 8 6 9 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
8
8 5 6 3 2 1 4 7
28
2 7 3 5 9 6 11 8 16 14 4 10 1 13 19 15 12 17 18 21 28 25 23 20 24 22 27 26
24
4 2 3 8 6 10 5 11 9 14 7 12 13 18 15 16 1 17 19 24 21 22 20 23
24
2 3 1 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
20
5 2 3 4 9 6 7 8 10 11 15 12 17 14 19 13 16 18 20 1
0

AC output:

Code: Select all

Set 1:
31
Set 2:
46
Set 3:
4
Set 4:
0
Set 5:
4
Set 6:
9
Set 7:
24
Set 8:
20
Set 9:
18
Set 10:
20
Set 11:
42
Set 12:
25
Set 13:
11
Set 14:
16
Set 15:
15
Set 16:
30
Set 17:
0
Set 18:
2
Set 19:
20
Set 20:
27
Set 21:
4
Set 22:
9
Set 23:
21
Set 24:
19
Set 25:
16
Set 26:
8
Set 27:
9
Set 28:
3
Set 29:
12
Set 30:
44
Set 31:
13
Set 32:
13
Set 33:
35
Set 34:
7
Set 35:
1
Set 36:
16
Set 37:
39
Set 38:
47
Set 39:
12
Set 40:
37
Set 41:
4
Set 42:
35
Set 43:
26
Set 44:
11
Set 45:
14
Set 46:
39
Set 47:
22
Set 48:
2
Set 49:
11