海洋之心


私信TA

用户名:wanggongsheng

访问量:131869

签 名:

等  级
排  名 18
经  验 21557
参赛次数 3
文章发表 163
年  龄 26
在职情况 学生
学  校
专  业 计算机技术

  自我简介:

读研ing,平时不登录dotcpp

#include<cstdio>
#include<cstring>
#include<set>
using namespace std;

typedef int State[9];
const int MAXSTATE = 1000000;
State st[MAXSTATE], goal;
int dist[MAXSTATE];

set<int> vis;
void init_lookup_table() { vis.clear(); }
int try_to_insert(int s) {
  int v = 0;
  for(int i = 0; i < 9; i++) v = v * 10 + st[s][i];
  if(vis.count(v)) return 0;
  vis.insert(v);
  return 1;
}

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int bfs() {
  init_lookup_table();
  int front = 1, rear = 2;
  while(front < rear) {
    State& s = st[front];
    if(memcmp(goal, s, sizeof(s)) == 0) return front;
    int z;
    for(z = 0; z < 9; z++) if(!s[z]) break;
    int x = z/3, y = z%3;
    for(int d = 0; d < 4; d++) {
      int newx = x + dx[d];
      int newy = y + dy[d];
      int newz = newx * 3 + newy;
      if(newx >= 0 && newx < 3 && newy >= 0 && newy < 3) {
        State& t = st[rear];
        memcpy(&t, &s, sizeof(s));
        t[newz] = s[z];
        t[z] = s[newz];
        dist[rear] = dist[front] + 1;
        if(try_to_insert(rear)) rear++;
      }
    }
    front++;
  }
  return 0;
}

int main() {
    char str[9];
    scanf("%s",str);
    for(int i=0;i<9;i++) //st[1]是初始状态
    if( str[i] !='.' ) st[1][i]=str[i]-'0';
    else st[1][i]=0;
    scanf("%s",str);
    for(int i=0;i<9;i++)//goal 是目标状态
    if(str[i]!='.')  goal[i]=str[i]-'0';
    else goal[i]=0;
  int ans = bfs();
  if(ans > 0) printf("%d\n", dist[ans]);
  else printf("-1\n");
  return 0;
}


 

0.0分

4 人评分

  评论区

。。。佛了,直接抄《算法竞赛入门》
2019-10-28 00:11:02
????
2019-01-26 10:25:46
这是啥啊。。c++说是c全放c++算了
2018-12-22 23:01:44
C描述要放C++,C++描述要放两个C++,怎么不把Java描述也放个C++??
2018-11-07 21:48:54
为什么是用bfs呢
2018-02-25 00:36:58
  • «
  • 1
  • »