fork download

copy

/*
Author：yew1eb Current Time: 2014.2.19
 
hdu1043 Eight
因为状态总数不多，只有不到40万种(9!)，因此可以从目标节点开始，
进行一遍彻底的广搜，找出全部有解状态到目标节点的路径。
 
状态判重：
cantor展开
 
注意有多解！！Special Judge
*/
 
#include <cstdio>
#include <cstring>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;
const int MAXN = 400000;
const int n = 9;
struct node {
    int s[9];
    int loc;
    int hf;
    string path;
} st;
 
 
int fac[9]= {1,1,2,6,24,120,720,5040,40320};
 
int cantor(int *a)
{
    int ans, i, j, tmp;
    ans = 0;
    for(i=0; i<n; ++i) {
        tmp = 0;
        for(j=i+1; j<n; ++j) if(a[j]<a[i]) tmp++;
        ans += fac[n-i-1]*tmp;
    }
    return ans + 1;
}
 
string path[MAXN];
bool vis[MAXN];
 
int dir[4][2]= {{-1,0},{1,0},{0,-1},{0,1}}; //u,d,l,r
char index[5]="durl";//和上面的要相反，因为是反向搜索:便于输出
 
void bfs()
{
    int i, j;
    queue<node> q;
    node cur, next;
    for(i=1; i<n; ++i) st.s[i-1] = i % n;
    st.loc = 8;
    st.path = "";
    st.hf = cantor(st.s);
    memset(vis, 0, sizeof vis );
    vis[st.hf] = 1;
    q.push(st);
    int tx, ty, dx, dy;
    while(!q.empty()) {
        cur = q.front();
        q.pop();
        tx = cur.loc / 3;
        ty = cur.loc % 3;
        for(i=0; i<4; ++i) {
            dx = tx + dir[i][0];
            dy = ty + dir[i][1];
            if(dx<0||dx>2||dy<0||dy>2) continue;
            next = cur;
            next.loc = dx*3 + dy;
            next.s[cur.loc] = next.s[next.loc];
            next.s[next.loc] = 0;
            next.hf = cantor(next.s);
            if(!vis[next.hf]) {
                vis[next.hf] = 1;
                next.path = index[i] + next.path;
                q.push(next);
                path[next.hf] = next.path;
            }
        }
    }
}
 
int main()
{
    char str[100];
    int len, i, j, cnt;
    node t;
    bfs();
    while(gets(str)) {
        len = strlen(str);
        cnt = 0;
        for(i=0; i<len; ++i) {
            if(str[i]>='1' && str[i]<='8')
                t.s[cnt++] = str[i] - '0';
            else if(str[i] == 'x') {
                t.s[cnt] = 0;
                t.loc = cnt++;
            }
        }
 
        t.hf = cantor(t.s);
        if(vis[t.hf]) {
            printf("%s\n",path[t.hf].c_str());
        } else {
            printf("unsolvable\n");
 
        }
    }
    return 0;
}
 
 
 
 
 
 
 
 
 
 
 
 
 

prog.cpp:48:13: error: ‘char index [5]’ redeclared as different kind of symbol
 char index[5]="durl";//和上面的要相反，因为是反向搜索:便于输出
             ^
In file included from /usr/include/c++/4.8/cstring:42:0,
                 from prog.cpp:15:
/usr/include/string.h:478:1: error: previous declaration of ‘const char* index(const char*, int)’
 index (const char *__s, int __c) __THROW
 ^
prog.cpp: In function ‘void bfs()’:
prog.cpp:79:36: error: invalid types ‘<unresolved overloaded function type>[int]’ for array subscript
                 next.path = index[i] + next.path;
                                    ^
prog.cpp:52:12: warning: unused variable ‘j’ [-Wunused-variable]
     int i, j;
            ^
prog.cpp: In function ‘int main()’:
prog.cpp:93:11: warning: ‘char* gets(char*)’ is deprecated (declared at /usr/include/stdio.h:638) [-Wdeprecated-declarations]
     while(gets(str)) {
           ^
prog.cpp:93:19: warning: ‘char* gets(char*)’ is deprecated (declared at /usr/include/stdio.h:638) [-Wdeprecated-declarations]
     while(gets(str)) {
                   ^
prog.cpp:90:17: warning: unused variable ‘j’ [-Wunused-variable]
     int len, i, j, cnt;
                 ^

Standard output is empty