V8SORT spoj – sắp xếp

2. Gợi ý V8SORT spoj

Ta để ý, số phần tử không quá 7.

Có bạn bảo là quay lui. Nhưng mình vẫn chưa nghĩ ra phải quay thế nào và khi nào thì dừng lại.

Ở đây mình gợi ý giải bằng phương pháp đồ thị. Ta đưa về bài toán tìm đường đi ngắn nhất với trọng số không âm. Sử dụng Dijkstra.

Ví dụ test mẫu, ta coi trạng thái dãy 1,2,3,4,6,5 là một đỉnh có chỉ số 123465 thì đỉnh kề với nó có thể là 213465(chi phí c12) , 321465(chi phí c13), 423165(chi phí c14),… (đổi chỗ 2 kí tự).

Để xây dựng được đồ thị, ta cần nén dãy ban đầu lại thành n phần tử có giá trị từ 1 -> n

=> sắp xếp để dãy thành 1,2,3,4,…,n. Sau đó ta chuyển trạng thái của dãy thành 1 đỉnh có chỉ số tạo thành bởi cách viết liên tiếp dãy đó. Để chuyển thì các bạn có thể viết 1 hàm riêng hoặc trong C có thể sử dụng hàm có sẵn. Vì n<=7 nên ta có max là 7654321 đỉnh.

3. Code mẫu V8SORT spoj

#include <bits/stdc++.h>
 
using namespace std;
typedef pair<int,int> II;
    char s[7];
    int a[10],n,f[7654325],x[10],cl[7654325],c[10][10];
    set<II> q;
int taoso()
{
    int u=0;
    for(int i=1; i<=n; i++)
        u=u*10+a[i];
    return u;
}
int taoen()
{
    int u=0;
    for(int i=1; i<=n; i++)
        if(a[i])
            u=u*10+i;
        else u=u*10;
    return u;
}
bool ok(int u,int i,int j)
{
    if(i==j) return 0;
    sprintf(s,"%d",u);
    if(s[i-1]=='0'||s[j-1]=='0')
        return 0;
    return 1;
}
int doi(int u,int i,int j)
{
    sprintf(s,"%d",u);
    swap(s[i-1],s[j-1]);
    sscanf(s,"%d",&u);
    return u;
}
void dij()
{
    int u,v;
    II t;
    int st=taoso();
    int en=taoen();
    cl[st]=1;
    f[st]=0;
    q.insert(II(0,st));
    while(!q.empty())
    {
        t=*q.begin();
        q.erase(t);
        u=t.second;
        if(u==en)
            {
                printf("%d",f[u]);
                return;
            }
        for(int i=1; i<=7; i++)
        for(int j=1; j<=7; j++)
            if(ok(u,i,j))
            {
                v=doi(u,i,j);
                if(cl[v]==0)
                {
                    cl[v]=1;
                    f[v]=f[u]+c[i][j];
                    q.insert(II(f[v],v));
                } else
                if(f[v]>f[u]+c[i][j])
                {
                    q.erase(II(f[v],v));
                    f[v]=f[u]+c[i][j];
                    q.insert(II(f[v],v));
                }
            }
    }
}
int main()
{
    //freopen("v8sort.inp","r",stdin);
    ios::sync_with_stdio(0);
    n=0;
    gets(s);
    char* st=strtok(s," ");
    while(st!=NULL)
    {
        sscanf(st,"%d",&a[++n]);
        x[n]=a[n];
        st=strtok(NULL," ");
    }
    sort(x+1,x+n+1);
    for(int i=1; i<=n; i++)
        a[i]=lower_bound(x+1,x+n+1,a[i])-x;
    for(int i=1; i<=n; i++)
    for(int j=1; j<=n; j++)
        scanf("%d",&c[i][j]);
    while(n<7)
        a[++n]=0;
    dij();
}