89 条题解
-
3
larryzhong LV 9 @ 2017-05-18 13:14:38
和 P1360 八数码问题 很像, 暴力广搜 + map 判重.
AC 代码:#include <iostream> #include <queue> #include <map> using namespace std; int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; struct matrix { int arr[4][4]; bool operator < (const matrix &other) const { for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) { if (arr[i][j] < other.arr[i][j]) return true; if (arr[i][j] > other.arr[i][j]) return false; } return false; } }; int main() { matrix start, _end; for (int i = 0; i < 4; i++) { string input; cin >> input; for (int j = 0; j < 4; j++) start.arr[i][j] = input[j] - '0'; } for (int i = 0; i < 4; i++) { string input; cin >> input; for (int j = 0; j < 4; j++) _end.arr[i][j] = input[j] - '0'; } queue<matrix> que; map<matrix, int> steps; que.push(start); steps[start] = 0; while (!que.empty() && steps.find(_end) == steps.end()) { matrix front = que.front(); que.pop(); for (int x0 = 0; x0 < 4; x0++) for (int y0 = 0; y0 < 4; y0++) for (int i = 0; i < 4; i++) { int x = x0 + dx[i]; int y = y0 + dy[i]; if (x >= 0 && x < 4 && y >= 0 && y < 4) { matrix push = front; swap(push.arr[x0][y0], push.arr[x][y]); if (steps.find(push) == steps.end()) { que.push(push); steps[push] = steps[front] + 1; } } } } cout << steps[_end] << endl; return 0; } -
1
写了个相对清晰的题解= = 供参考
/** * 简单BFS+二进制即可 * * 顺便问问那些变量命名全部是a b c d u v、没一个注释还发到题解区的dalao们，你们的良心不会痛么 (= =) * * */ #include <stdio.h> #include <inttypes.h> #define QUEUE_MAX 200000 //取出num的第i位 #define get(num, i) (((num) >> (15 - (i)))&1) //返回第i位取反后的num #define flip(num, i) ((num) ^ (1 << (15 - (i)))) /* * 从第i位出发可交换的位置，-1表示不可交换 * 0 1 2 3 * 4 5 6 7 * 8 9 10 11 * 12 13 14 15 * */ int stepMap[16][2] = { {1, 4}, {2, 5}, {3, 6}, {7, -1}, {5, 8}, {6, 9}, {7, 10}, {11, -1}, {9, 12}, {10, 13}, {11, 14}, {15, -1}, {13, -1}, {14, -1}, {15, -1}, {-1, -1} }; //原队列中是否存在num uint_fast8_t contains(const uint_fast16_t queue[QUEUE_MAX][2], uint_fast16_t num, int tail) { for (int i = 0; i < tail; i++) { if (queue[i][0] == num)return 1; } return 0; } int main() { //queue中每个位置储存一个状态和一个行走步数；goal即为目标 uint_fast16_t queue[QUEUE_MAX][2] = {0}, goal = 0; int head = 0, tail = 1; char str[10]; //读入数据 for (int i = 0; i < 4; i++) { gets(str); for (int j = 0; j < 4; j++) { queue[0][0] += (str[j] - '0') << (15 - i * 4 - j); } } gets(str); for (int i = 0; i < 4; i++) { gets(str); for (int j = 0; j < 4; j++) { goal += (str[j] - '0') << (15 - i * 4 - j); } } //第二个测试点的起点即为答案 (= _ =) if (queue[0][0] == goal) { printf("0"); return 0; } //队列尚未结束 while (head < tail) { //依次考虑0-15位的交换 for (int i = 0; i < 16; i++) { for (int j = 0; j < 2; j++) { if (stepMap[i][j] >= 0 && get(queue[head][0], i) != get(queue[head][0], stepMap[i][j])) { //交换两个位置 uint_fast16_t flipped = flip(flip(queue[head][0], i), stepMap[i][j]); //如果没有重复的，加入队列尾部 if (!contains(queue, flipped, tail)) { queue[tail][0] = flipped; queue[tail][1] = queue[head][1] + 1; //如果到达结果，输出并停止程序 if (queue[tail][0] == goal) { printf("%"PRIuFAST16, queue[tail][1]); return 0; } tail++; } } } } //处理下一个 head++; } return 0; } -
1
BFS+MAP判重
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<iostream> #include<vector> #include<queue> #include<map> using namespace std; const uint16_t factor[]={32768,16384,8192,4096,2048,1024,512,256,128,64,32,16,8,4,2,1}; int init[16],target[16]; uint16_t initc,targc; int d[2][4]={{0,0,-1,1}, //左，右，上，下 {-1,1,0,0}}; map<uint16_t,int> m; queue<uint16_t> q; uint16_t encode(int *a){ uint16_t code=0; for(int i=0;i<16;i++){ code *= 2; code += a[i]; } return code; } uint16_t exchange(uint16_t cur,int pos1,int pos2){ uint16_t next = cur^factor[pos1]^factor[pos2]; return next; } void bfs(){ uint16_t cur; while(!q.empty()){ cur = q.front(); for(int i=0;i<16;i++){ int curx=i/4, cury= i%4; for(int j=0;j<4;j++){ uint16_t next; int x = curx + d[0][j]; int y = cury + d[1][j]; if(x<0||x>3||y<0||y>3) continue; int pos1 =4*x+y, pos2 = 4*curx+cury; if(((cur&factor[pos1])>>(15-pos1)) == ((cur&factor[pos2])>>(15-pos2))) continue; else next = exchange(cur,pos1,pos2); if(!m.count(next)){ m[next]=m[cur]+1; q.push(next); if(next==targc){ cout<<m[next]; return; } } } } q.pop(); } } int main(){ int temp; for(int i=0;i<4;i++){ scanf("%d",&temp); for(int j=3;j>=0;j--){ init[4*i+j] = temp%10; temp /= 10; } } for(int i=0;i<4;i++){ scanf("%d",&temp); for(int j=3;j>=0;j--){ target[4*i+j] = temp%10; temp /= 10; } } initc = encode(init); targc = encode(target); m[initc] = 0; q.push(initc); if(initc==targc){ cout<<0; return 0; } bfs(); return 0; } -
1
比较容易的一道广搜，由于状态比较少我们可以直接二进制压位来存储状态（险些用康拓展开的人）
主要是压缩和解压缩的过程#include<iostream> using namespace std; int minn[1<<16],dui[1<<16],map[4][4],xin[4][4]; int main() { char a; int i,j,chu=0,mo=0,head,tail,now,u,v,ha,lin,x,y,temp; for(i=0;i<4;i++) for(j=0;j<4;j++) { cin>>a; chu*=2; chu+=a-'0'; } for(i=0;i<4;i++) for(j=0;j<4;j++) { cin>>a; mo*=2; mo+=a-'0'; } //cout<<chu<<" "<<mo<<endl; head=1; tail=1; dui[1]=chu; minn[dui[1]]=1; while(tail<=head) { ha=dui[tail]; if(ha==mo) break; for(i=3;i>=0;i--) for(j=3;j>=0;j--) { map[i][j]=ha&1; ha/=2; } for(i=0;i<4;i++) for(j=0;j<4;j++) { if(j<3&&map[i][j]!=map[i][j+1]) { lin=0; temp=map[i][j]; map[i][j]=map[i][j+1]; map[i][j+1]=temp; for(u=0;u<4;u++) for(v=0;v<4;v++) { lin*=2; lin+=map[u][v]; } if(!minn[lin]) { head++; dui[head]=lin; minn[lin]=minn[dui[tail]]+1; } temp=map[i][j]; map[i][j]=map[i][j+1]; map[i][j+1]=temp; } if(i<3&&map[i][j]!=map[i+1][j]) { lin=0; temp=map[i][j]; map[i][j]=map[i+1][j]; map[i+1][j]=temp; for(u=0;u<4;u++) for(v=0;v<4;v++) { lin*=2; lin+=map[u][v]; } if(!minn[lin]) { head++; dui[head]=lin; minn[lin]=minn[dui[tail]]+1; } temp=map[i][j]; map[i][j]=map[i+1][j]; map[i+1][j]=temp; } } tail++; } cout<<minn[dui[tail]]-1; return 0; } -
0
#include<stdio.h>
#include<stdlib.h>
using namespace std;const int nn=4;
//算法：从起点和终点同时开始宽搜，对着搜
//二叉查找树判重
struct node{
bool a[nn][nn];//一个状态
short step;//最小步数
node *next;
};
//用一个二进制数表示一个状态
int hash(node *p)
{
int i,j;
int n=0;
for(i=0;i<nn;i++)
for(j=0;j<nn;j++)
{
n=n<<1;
n=n|p->a[i][j];
}
return n;
}//二叉查找树的节点
struct node2{
int a;//节点的状态
short step;//到达节点的步数
node2 *left;
node2 *right;
};//判断能否做移动
//移动方向：0上，3下，1左，2右
//搜索中，每次只移动空白的格子
bool movable(node *p,int x,int y,int k)
{
//只移动空白格子
if(p->a[x][y]==1)
return 0;
//不能越界
if((x==nn-1)&&(k==3))
return 0;
if((x==0)&&(k==0))
return 0;
if((y==0)&&(k==1))
return 0;
if((y==nn-1)&&(k==2))
return 0;
//空白格子不和空白格子交换
if((k==3)&&(p->a[x+1][y]==0))
return 0;
if((k==0)&&(p->a[x-1][y]==0))
return 0;
if((k==1)&&(p->a[x][y-1]==0))
return 0;
if((k==2)&&(p->a[x][y+1]==0))
return 0;
return 1;
}
//拓展head节点，结果存在tail节点当中
void move(node *head,node *tail,int x,int y,int k)
{
int i,j;
for(i=0;i<nn;i++)
for(j=0;j<nn;j++)
tail->a[i][j]=head->a[i][j];
switch(k){
case 0:{
tail->a[x-1][y]=0;
break;
}
case 1:{
tail->a[x][y-1]=0;
break;
}
case 2:{
tail->a[x][y+1]=0;
break;
}
case 3:{
tail->a[x+1][y]=0;
break;
}
}
tail->a[x][y]=1;
tail->step=head->step+1;
tail->next=NULL;
}
//在二叉查找树中寻找一个元素。若是找到，则返回1；
//若是没有找到，则返回0，并插入该元素
bool search_insert(int l,short step,node2 *head)
{
node2 *p,*q;
p=head;
q=head;
while(q!=NULL)
{
p=q;
if(l<p->a)
q=p->left;
if(l>p->a)
q=p->right;
if(l==p->a) return 1;
}
if(q==NULL)
{
q=new node2;
if(l>p->a)
p->right=q;
if(l<p->a)
p->left=q;
q->left=NULL;
q->right=NULL;
q->a=l;
q->step=step;
return 0;
}
}
//在查找树中寻找元素，没找到返回0//
int search(int l,node2 *head)
{
node2 *p,*q;
p=head;
q=head;
while(q!=NULL)
{
p=q;
if(l==p->a) return (int) p->step;
if(l<p->a)
q=p->left;
if(l>p->a)
q=p->right;
}
if(q==NULL)
return 0;
}
//递归释放查找树
void release(node2 *head)
{
if(head->left!=NULL)
release(head->left);
if(head->right!=NULL)
release(head->right);
delete head;
}
int main()
{
int i,j,k;
node *head1,*tail1,*head2,*tail2,*p;//两条宽搜队列
node2 *hash1,*hash2; //两个查找树
int l,l0; //用于储存hash的结果，l0表示两条搜索树相遇的状态
char ch;//初始节点，队头
head1=new node;
for(i=0;i<nn;i++)
{
for(j=0;j<nn;j++)
{
scanf("%c",&ch);
head1->a[i][j]=(bool)(ch-'0');
}
scanf("%c",&ch);
}
scanf("%c",&ch);
head1->next=NULL;
head1->step=0;
tail1=head1;
//初始节点加入查找树
hash1=new node2;
hash1->a=hash(head1);
hash1->step=0;
hash1->left=NULL;
hash1->right=NULL;
//目标节点，队头
head2=new node;
for(i=0;i<nn;i++)
{
for(j=0;j<nn;j++)
{
scanf("%c",&ch);
head2->a[i][j]=(bool)(ch-'0');
}
scanf("%c",&ch);
}
head2->next=NULL;
head2->step=0;
tail2=head2;
//目标节点加入查找树
hash2=new node2;
hash2->a=hash(head2);
hash2->step=0;
hash2->left=NULL;
hash2->right=NULL;l0=-1;//标记两个搜索树未相遇。
if(hash(head2)==hash(head1))
l0=hash(head1);
while(l0==-1)
{
if(head1!=NULL)
{
//从初始状态开始搜索
for(i=0;(i<nn)&&(l0==-1);i++)
for(j=0;(j<nn)&&(l0==-1);j++)//i，j是16个节点位置
for(k=0;(k<4)&&(l0==-1);k++)//k是移动方向
if(movable(head1,i,j,k)==1)
{
p=new node;
move(head1,p,i,j,k);
//如果新的状态节点与已有的节点重复，则不加入搜索队列
l=hash(p);
if(search_insert(l,p->step,hash1)==1)
delete p;
else{
//加入搜索队列
tail1->next=p;
tail1=p;
}
//判断搜索树是否相遇
if(search(l,hash2)>0)
l0=l;
}
//释放已经被搜索过的队头
p=head1;
head1=head1->next;
delete p;if(l0>0)
break;
}
if(head2!=NULL)
{
//从目标状态开始搜索，基本过程和上文一致
for(i=0;(i<nn)&&(l0==-1);i++)
for(j=nn-1;(j>=0)&&(l0==-1);j--)
for(k=0;(k<4)&&(l0==-1);k++)
if(movable(head2,i,j,k)==1)
{
p=new node;
move(head2,p,i,j,k);
l=hash(p);
if(search_insert(l,p->step,hash2)==1)
delete p;
else{
tail2->next=p;
tail2=p;
}
//判断搜索树是否相遇
if(search(l,hash1)>0)
l0=l;
}
p=head2;
head2=head2->next;
delete p;
}
}
k=search(l0,hash1)+search(l0,hash2);
printf("%d\n",k);
//释放所有链表
release(hash1);
release(hash2);
while(head1!=NULL)
{
p=head1;
head1=head1->next;
delete p;
}
while(head2!=NULL)
{
p=head2;
head2=head2->next;
delete p;
}
} -
0
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <ctype.h>
#define SIZE 17struct node {
char data[SIZE];
struct node *next;
};typedef struct queue{
struct node *first;
struct node *last;
int size;
}_queue;int visit[65536];
int pre[65536];
int xx[24] = {0,1,2,4,5,6,8,9,10,12,13,14,0,1,2,3,4,5,6,7,8,9,10,11};
int yy[24] = {1,2,3,5,6,7,9,10,11,13,14,15,4,5,6,7,8,9,10,11,12,13,14,15};bool qempty(_queue *q);
_queue *qnew();
void qpush(_queue *q, char str[]);
char *qpop(_queue *q);
int convert(char str[]);
void bfs(char start[], char end[]);
char *show(_queue *q);int main() {
char ch, start[SIZE], end[SIZE];
int i;
for (i = 0 ; i < SIZE -1; ) {
ch = getchar();
if (ch == '0' || ch == '1') {
start[i++] = ch;
}
}
start[i] = '\0';for (i = 0 ; i < SIZE -1; ) {
ch = getchar();
if (ch == '0' || ch == '1') {
end[i++] = ch;
}
}
end[i] = '\0';bfs(start, end);
return 0;
}void bfs(char start[], char end[]) {
_queue *q = qnew();
char str[17], tmp[17], ch;
int i;
if (strcmp(start, end) == 0) {
printf("0\n");
return;
}qpush(q, start);
visit[convert(start)] = 1;while (!qempty(q)) {
strcpy(str, qpop(q));
if (strcmp(str, end) == 0) {
break;
}// printf("%s\n", str);
for (i = 0 ; i < 24; i++) {
if (str[xx[i]] - '0' + str[yy[i]] - '0' == 1) {
strcpy(tmp,str);
ch = tmp[xx[i]];
tmp[xx[i]] = tmp[yy[i]];
tmp[yy[i]] = ch;
if (!visit[convert(tmp)]) {
visit[convert(tmp)] = 1;
qpush(q, tmp);
pre[convert(tmp)] = convert(str);
}
}
}
}int st, ed, step = 0;
st = convert(start);
ed = convert(end);
while (pre[ed] != st) {
ed = pre[ed];
step++;
}
printf("%d\n", step + 1);}
char *show(_queue *q) {
static char str[17];
strcpy(str, q->first->data);
return str;
}void qpush(_queue *q, char str[]) {
struct node *p = (struct node *) malloc(sizeof(struct node));
p->next = NULL;
strcpy(p->data, str);if (qempty(q)) {
q->size++;
q->first = q->last = p;
return;
}
q->size++;
q->last->next = p;
q->last = p;}
int convert(char str[]) {
int number = 0;
int i;
for (i = SIZE - 2 ; i >= 0; i--) {
if (str[i] == '1')
number = number + (1 << (15 - i));
}
return number;
}char *qpop(_queue *q) {
static char str[17];
strcpy(str, q->first->data);
struct node *p = q->first;
q->size--;
if (qempty(q)) {
q->last = q->first = q->first->next;
free(p);
return str;
}
q->first = q->first->next;
free(p);
return str;
}_queue *qnew() {
_queue *q = (_queue *) malloc (sizeof(_queue));
q->first = NULL;
q->last = q->first;
q->size = 0;
return q;
}bool qempty(_queue *q) {
return q->size == 0 ? true : false;
} -
0
思路简单，暴力BFS,
判重部分，因为16个格子均为0和1，所以可以把整个矩阵转换为一个二进制数
这个二进制数最大为十六位1（十进制65535），所以用一个bool形数组visited[65535]判重
读入时用一个string读入四个格子,再逐一转换成数字
上代码
```cpp
#include <iostream>
#include <queue>
#include <cmath>
using namespace std;struct matrix{
int a[4][4];
int step;
int decimal;
};struct pos{
int x,y;
};int start[4][4] , en[4][4];
bool visited[65536] = {false};
queue<matrix> q;
int mov[4][2] = {{1,0},{0,1},{0,-1},{-1,0}};int to_decimal(matrix m){
int result = 0;
int k = 15;
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
result += (int)pow(2,k--) * m.a[i][j];
}
}
return result;
}bool is_visited(matrix m){
if(visited[m.decimal])
return true;
else{
visited[m.decimal] = true;
return false;
}
}bool check(matrix m){
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
if(m.a[i][j] != en[i][j])
return false;
}
}
return true;
}void move(matrix m){
int x,y,u,v,temp;
matrix t;
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
for (int k = 0; k < 2; ++k) {
t = m;
u = i + mov[k][0];
v = j + mov[k][1];
if(u<0 || u >= 4 || v<0 || v>=4)
continue;
temp = t.a[u][v];
t.a[u][v] = t.a[i][j];
t.a[i][j] = temp;
t.step ++;
t.decimal = to_decimal(t);
if(!is_visited(t)){
q.push(t);
}
}
}
}
}int bfs(){
matrix m;
while(!q.empty()){
m = q.front();
q.pop();
if(check(m))
return m.step;
move(m);
}
}int main()
{
string s;
for (int i = 0; i < 4; ++i) {
cin >> s;
for (int j = 0; j < 4; ++j) {
start[i][j] = s[j] - '0';
}
}
for (int i = 0; i < 4; ++i) {
cin >> s;
for (int j = 0; j < 4; ++j) {
en[i][j] = s[j] - '0';
}
}matrix m;
m.step = 0;
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
m.a[i][j] = start[i][j];
}
}
m.decimal = to_decimal(m);
visited[m.decimal] = true;
q.push(m);
cout << bfs() << endl;return 0;
}
``` -
0
找每两点的关系，转换成
8x8的数组，然后dfs即可#include<iostream> #include<cstdio> #include<cstring> #include<cmath> # include<algorithm> using namespace std; char a[5][5],b[5][5]; int c[9][3],d[9][3],e[9][9],v[9],w=99999; long long ans,q=0; void dfs(int t) { if(t==9) { if(ans<w)w=ans; } for(int i=1;i<=8;i++) { if(v[i]==0) { ans+=e[t][i]; v[i]=1; dfs(t+1); v[i]=0; ans-=e[t][i]; } } } int main() { for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) { cin>>a[i][j]; if(a[i][j]=='1') { q++; d[q][1]=i; d[q][2]=j; } } q=0; for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) { cin>>b[i][j]; if(b[i][j]=='1'){q++;c[q][1]=i;c[q][2]=j; }} q=0; for(int j=1;j<=8;j++) for(int i=1;i<=8;i++) e[i][j]=abs(c[i][1]-d[j][1])+abs(c[i][2]-d[j][2]); dfs(1); cout<<w<<endl; //while(1); return 0; }编译成功
测试数据 #0: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 560 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 560 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 564 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 564 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 560 KiB, score = 10
Accepted, time = 45 ms, mem = 564 KiB, score = 100
-
0
八个循环的爆搜
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> # include<algorithm> using namespace std; char a[5][5],b[5][5]; int c[9][3]={0},d[9][3]={0},e[9][9],g[9],w=99999; long long ans[99999],q=0; int main() { for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) { cin>>a[i][j];if(a[i][j]=='1'){q++;d[q][1]=i;d[q][2]=j;} } q=0; for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) { cin>>b[i][j]; if(b[i][j]=='1'){q++;c[q][1]=i;c[q][2]=j; }} q=0; for(int j=1;j<=8;j++) for(int i=1;i<=8;i++) e[i][j]=abs(c[i][1]-d[j][1])+abs(c[i][2]-d[j][2]); /* for(int j=1;j<=8;j++) { for(int i=1;i<=8;i++) cout<<e[i][j]<<" "; cout<<endl;} */ for(int i1=1;i1<=8;i1++) for(int i2=1;i2<=8;i2++) for(int i3=1;i3<=8;i3++) for(int i4=1;i4<=8;i4++) for(int i5=1;i5<=8;i5++) for(int i6=1;i6<=8;i6++) for(int i7=1;i7<=8;i7++) for(int i8=1;i8<=8;i8++) { if(i2!=i1&&i3!=i2&&i3!=i1&&i4!=i3&&i4!=i2&&i4!=i1&&i5!=i4&&i5!=i3&&i5!=i2&&i5!=i1&&i6!=i5&&i6!=i4&&i6!=i3&&i6!=i2&&i6!=i1&& i7!=i6&&i7!=i5&&i7!=i4&&i7!=i3&&i7!=i2&&i7!=i1&&i8!=i7&&i8!=i6&&i8!=i5&&i8!=i4&&i8!=i3&&i8!=i2&&i8!=i1) { q++; ans[q]=e[i1][1]+e[i2][2]+e[i3][3]+e[i4][4]+e[i5][5]+e[i6][6]+e[i7][7]+e[i8][8]; if(ans[q]<w)w=ans[q]; } } cout<<w; return 0; } -
0
暴力BFS丝毫不虚
状态只有2^16，用hash判个重就丝毫不虚#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) #define maxn 1000010 using namespace std; typedef long long llg; int a[4][4],mu,b[4][4]; int d[maxn],l,r,de[maxn]; int zx[2]={1,0},zy[2]={0,1}; bool w[maxn]; char s[5]; int ya(){ int now=0; for(int i=0;i<4;i++) for(int j=0;j<4;j++) now<<=1,now+=a[i][j]; return now; } void jie(int x){ for(int i=3;i>=0;i--) for(int j=3;j>=0;j--) a[i][j]=x&1,x>>=1; } int main(){ File("a"); for(int i=0;i<4;i++){ scanf("%s",s); for(int j=0;j<4;j++) a[i][j]=s[j]-'0'; } d[r++]=ya(); w[d[0]]=1; for(int i=0;i<4;i++){ scanf("%s",s); for(int j=0;j<4;j++) a[i][j]=s[j]-'0'; } mu=ya(); if(mu==d[0]){printf("0");return 0;} while(l!=r){ int xx=de[l],u=d[l++],v; jie(u); for(int i=0;i<4;i++) for(int j=0;j<4;j++) for(int k=0;k<2;k++){ int x=i+zx[k],y=j+zy[k]; if(x>=0 && x<4 && y>=0 && y<4){ swap(a[i][j],a[x][y]); v=ya(); if(v==mu){printf("%d",xx+1);return 0;} if(!w[v]) w[v]=1,de[r]=xx+1,d[r++]=v; swap(a[i][j],a[x][y]); } } } } -
0
我勒个去，编的麻烦死了。
其实就是读入两个方格+宽搜，只是判重注意一下。
我用数字判重，因为只有65536种情况嘛。
我和楼下的大神一起做，看我做的多慢。
哎，因为刚转C++，妈的，光是读入调试了一个小时。
C++不是段异常就是爆机。
BY JSB 绍兴一中万岁！
#include<stdio.h>
using namespace std;
long f[65537]={65537};
char x[65537][17]={},a[17]={},now[17]={};
long y[65537]={0};
long ok,h,t,start,end,check,i,j,p,k,go,ans;
char temp,oo;
int main()
{
for (i=1;i<=65536;i++) f[i]=65537;
for (i=1;i<=16;i++)
{
scanf("%c",&oo);
a[i]=oo;
if (i%4==0) scanf("%c",&oo);
y[1]=y[1]*2+a[i]-48;
}
scanf("%c",&oo);
ok=0;
for (p=1;p<=16;p++)
x[1][p]=a[p];
f[y[1]]=0;
for (i=1;i<=16;i++)
{
scanf("%c",&oo);
a[i]=oo;
if (i%4==0) scanf("%c",&oo);
ok=ok*2+a[i]-48;
}
h=0;t=1;ans=0;
while (h<t)
{
h++;
for (p=1;p<=16;p++) now[p]=x[h][p];
check=y[h];
for (i=1;i<=4;i++)
for (j=1;j<=3;j++)
{
start=(i-1)*4+j;end=start+1;
temp=now[start];now[start]=now[end];now[end]=temp;
go=0;
for (k=1;k<=16;k++) go=go*2+now[k]-48;
if (f[go]==65537)
{
t++;
for (p=1;p<=16;p++) x[t][p]=now[p];
y[t]=go;f[go]=f[check]+1;
if (ok==go) ans=f[go];
}
temp=now[start];now[start]=now[end];now[end]=temp;
}
for (i=1;i<=3;i++)
for (j=1;j<=4;j++)
{
start=(i-1)*4+j;end=start+4;
temp=now[start];now[start]=now[end];now[end]=temp;
go=0;
for (k=1;k<=16;k++) go=go*2+now[k]-48;
if (f[go]==65537)
{
t++;
for (p=1;p<=16;p++) x[t][p]=now[p];
y[t]=go;f[go]=f[check]+1;
if (ok==go) ans=f[go];
}
temp=now[start];now[start]=now[end];now[end]=temp;
}
if (ans>0) break;
}
printf("%ld",ans);
return 0;
} -
0
因为这题是固定的4*4方格，把黑色的视为1，把白色的视为0；状态总共是16^4=65536种，太方便了，判重连hash都不用了。直接可以用数组判重，然后宽搜直接秒杀
#include<stdio.h>
using namespace std;
struct o{
bool map[5][5];
//4*4的01矩阵
};bool gone[70000]={false}; //用来判重的。
o que[100000];long top=0,tail=0;long ans=0;o start,end;long s,e;bool isend=false;
long zm(o a) //01矩阵转数字
{
long ans=0;
for(int i=1;i<=4;i++)
{ ans*=16;
for(int j=1;j<=4;j++)if(a.map[i][j]==true)ans+=1<<(j-1);
}
return ans;
}
o nzj(long a) //数字转01矩阵
{ o k;for(int i=1;i<=4;i++)for(int j=1;j<=4;j++)k.map[i][j]=false;
for(int i=4;i>=1;i--)
{
long y=a%16;a/=16;
for(int j=1;j<=4;j++)if((1<<(j-1))&y>0)k.map[i][j]=true;
}
return k;
}
void kz(o s) 根据S这个01矩阵进行宽搜扩展。isend表示是否有答案。
{
for(int i=1;i<=4;i++)for(int j=1;j<=4;j++)
{
if(j+1<=4){bool temp=s.map[i][j];s.map[i][j]=s.map[i][j+1];s.map[i][j+1]=temp;long zb=zm(s);
if(zb==e){printf("%ld",ans);isend=true;return;}
if(gone[zb]==false){gone[zb]=true;tail++;que[tail]=s;}
temp=s.map[i][j];s.map[i][j]=s.map[i][j+1];s.map[i][j+1]=temp;}
if(i+1<=4){bool temp=s.map[i][j];s.map[i][j]=s.map[i+1][j];s.map[i+1][j]=temp;long zb=zm(s);
if(zb==e){printf("%ld",ans);isend=true;return;}
if(gone[zb]==false){gone[zb]=true;tail++;que[tail]=s;}
temp=s.map[i][j];s.map[i][j]=s.map[i+1][j];s.map[i+1][j]=temp;}
}
}
int main()
{
for(int i=1;i<=4;i++){for(int j=1;j<=4;j++){char u;scanf("%c",&u);start.map[i][j]=(u=='1');}char s1;scanf("%c",&s1);}
char s1;scanf("%c",&s1);//中间有一个换行符
for(int i=1;i<=4;i++){for(int j=1;j<=4;j++){char u;scanf("%c",&u);end.map[i][j]=(u=='1');}char s1;scanf("%c",&s1);}
//以上部分是读入，这里得用char读入，要注意换行符！
s=zm(start);e=zm(end);gone[s]=true;if(s==e){printf("0");return 0;}
tail++;que[tail]=start;top++;
while(true) //宽搜走起！
{ans++;long u=tail;
for(long i=top;i<=u;i++){kz(que[i]);if(isend)return 0;}
top=u;
}
return 0;
} -
0
bool doit(int sa, int sb, int sc, int sd)
{
int ha;
if (sc>0 && sc<5 && sd>0 && sd<5 && a[sa][sb]!=a[sc][sd])
{
swap(a[sa][sb],a[sc][sd]);
ha=hash(a);
if (!v[ha]) list[tail]=ha, ans[tail]=ans[head]+1, tail++;
v[ha]=true;
swap(a[sa][sb],a[sc][sd]);
}
if (ha==js) return true;
return false;
}int bfs()
{
memset(v, 0, sizeof(v));
ans[1]=0; list[1]=cs;
while (head<tail)
{
int k=list[head];
if (k==js) return ans[head];
for (int i=4; i>=1; i--)
for (int j=4; j>=1; j--)
{
a[i][j]=k%2;
k/=2;
}
for (int i=1; i<=4; i++)
{
for (int j=1; j<=4; j++)
{
if (doit(i,j,i,j-1)) return ans[tail-1];
if (doit(i,j,i,j+1)) return ans[tail-1];
if (doit(i,j,i-1,j)) return ans[tail-1];
if (doit(i,j,i+1,j)) return ans[tail-1];
}
}
head++;
}
}//部分代码
-
0
追奇葩的hash
├ 测试数据 01：答案正确... (0ms, 20304KB)
├ 测试数据 02：答案正确... (0ms, 20304KB)
├ 测试数据 03：答案正确... (15ms, 20304KB)
├ 测试数据 04：答案正确... (14ms, 20304KB)
├ 测试数据 05：答案正确... (31ms, 20304KB)
├ 测试数据 06：答案正确... (15ms, 20304KB)
├ 测试数据 07：答案正确... (46ms, 20304KB)
├ 测试数据 08：答案正确... (31ms, 20304KB)
├ 测试数据 09：答案正确... (31ms, 20304KB)
├ 测试数据 10：答案正确... (31ms, 20304KB)type arr=array[1..16] of 0..1;
rec=record
l:longint;
s:arr;
end;
var a,b:arr;
i:integer;
q:array[1..1000000] of rec;
f,r:longint;
c:char;
h:array[0..1,0..1,0..1,0..1,0..1,0..1,0..1,0..1,0..1,0..1,0..1,0..1,0..1,0..1,0..1,0..1] of boolean;procedure add(x:arr);
begin
h[x[1],x[2],x[3],x[4],x[5],x[6],x[7],x[8],x[9],x[10],x[11],x[12],x[13],x[14],x[15],x[16]]:=true;
end;function have(x:arr):boolean;
begin
have:=h[x[1],x[2],x[3],x[4],x[5],x[6],x[7],x[8],x[9],x[10],x[11],x[12],x[13],x[14],x[15],x[16]];
end;procedure bfs;
function can(x,y:longint):boolean;
begin
if not((x+y=17)) then begin
if q[f].s[x]=q[f].s[x+y] then exit(false);
case x of
1:exit((y=4)or(y=1));
2,3:exit(y-4);
4:exit((y=-1)or(y=4));
5,9:exit(y-1);
6,7,10,11:exit(true);
8,12:exit(y1);
13:exit((y=1)or(y=-4));
14,15:exit(y4);
16:exit((y=-1)or(y=-4));
end;
end else can:=false;
end;
const c:array[1..4] of longint=(1,-1,4,-4);
var i,j:longint;
s:arr;
function deng:boolean;
var i:integer;
begin
for i:=1 to 16 do
if s[i]b[i] then exit(false);
exit(true);
end;
begin
s:=a;
if deng then begin writeln(0); halt; end;
f:=1; r:=1;
q[1].s:=a;
add(a);
repeat
for j:=1 to 16 do
for i:=1 to 4 do
if can(j,c[i]) then begin
s:=q[f].s;
s[j]:=1-s[j];
s[j+c[i]]:=1-s[j+c[i]];
if not have(s) then begin
inc(r);
q[r].l:=q[f].l+1;
q[r].s:=s;
add(s);
if deng then begin writeln(q[r].l); halt; end;
end;
end;
inc(f);
until f>r;
end;begin
for i:=1 to 16 do begin
read(c);
if i mod 4=0 then readln;
a[i]:=ord(c)-48;
end;
readln;
for i:=1 to 16 do begin
read(c);
if i mod 4=0 then readln;
b[i]:=ord(c)-48;
end;
readln;
bfs;
end. -
0
var hash:array[0..70000] of longint;
c:array[1..2,1..24] of integer=(...);
f:array[0..70000] of longint;
now,pre,aim,i,j,k,p,sum:longint;
s:string;procedure ready;
begin
sum:=0;
for i:=1 to 4 do
begin
readln(s);
for j:=1 to 4 do sum:=sum+(ord(s[j])-ord('0'))*trunc(exp(((i-1)*4+j-1)*ln(2)));
end;
pre:=sum;
readln(s);
sum:=0;
for i:=1 to 4 do
begin
readln(s);
for j:=1 to 4 do sum:=sum+(ord(s[j])-ord('0'))*trunc(exp(((i-1)*4+j-1)*ln(2)));
end;
aim:=sum;
end;begin
ready;
if pre=aim then begin writeln('0');halt;end;
f[1]:=pre;
k:=1;p:=1;
while f[k]>0 do
begin
for i:=1 to 24 do
if ((f[k] and (1 shl (c[1,i]-1))>0) and (f[k] and (1 shl (c[2,i]-1))=0)) or ((f[k] and (1 shl (c[1,i]-1))=0) and (f[k] and (1 shl (c[2,i]-1))>0))
then
beginnow:=f[k] xor (1 shl (c[1,i]-1));
now:=now xor (1 shl (c[2,i]-1));if now=aim then
begin
writeln(hash[f[k]]+1);
halt;
end;if hash[now]=0 then
begin
hash[now]:=hash[f[k]]+1;
inc(p);
f[p]:=now;
end;end;
inc(k);
end;
end.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
就50多行额。
bfs+位运算。 -
0
1oVe YoU疾风 LV 10 @ 2009-10-07 11:14:48
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0mstype
atp = record
data,time : longint;
end;
var
hash : array [0..70000] of boolean;
q : array [1..1000000*3] of atp;
st,ans : longint;procedure init;
var i , j : longint; str : string;
begin
ans := 0; st := 0;
for i := 1 to 4 do
begin
readln(str);
for j := 1 to 4 do st := st*2 + ord(str[j]) - 48;
end;
readln;
for i := 1 to 4 do
begin
readln(str);
for j := 1 to 4 do ans := ans*2 + ord(str[j]) - 48;
end;
end;function hashit(x : longint) : boolean;
begin if hash[x] then exit(false); hash[x] := true; exit(true); end;function swap(x,i,j : longint) : longint;
var k : longint;
begin exit(x - 1 shl (i-1) + 1 shl (j-1)); end;procedure main;
var i , j , x , l , r , k : longint; d,t : atp;
begin
q[1].time := 0; q[1].data := st; l := 1; r := 1; fillchar(hash,sizeof(hash),0);
hashit(st);
while l
larryzhong
LV 9
@ 2017-05-18 13:14:38
