F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:五月份月赛定于5.27日12:30--17:30,欢迎大家来玩! 2:关于OJ的注册可看https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671
大视野在线测评-欢迎您
[ New Thread ]
MainBoard >> 我女装刚学搜索没超时wa了有人能看看吗
xlu @ 2018-01-09 09:33:26
[ Quote ] [ Edit ] [ Delete ] 1#
#include<map>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 1e8
using namespace std;
char a[10][10]={"11111","01111","00*11","00001","00000"};
char b[10][10];
int state1,pos1,state2,pos2;
struct node{int state,pos,dis;};
int id[10][10];
const int f[8][2]={1,-2,1,2,2,1,2,-1,-1,2,-1,-2,-2,1,-2,-1};
int bfs()
{
queue<node>q1,q2;
map<pair<int,int>,int> m1,m2;
pair<int,int> p1,p2;
node now1,next1;
node now2,next2;
now1.state=state1;
now1.pos=pos1;
now1.dis=1;
q1.push(now1);
p1=make_pair(state1,pos1);
m1[p1]=1;
now2.state=state2;
now2.pos=pos2;
now2.dis=1;
q2.push(now2);
p2=make_pair(state2,pos2);
m2[p2]=1;
if(state1==state2&&pos1==pos2) return 0;
while(q1.size()&&q2.size())
{
now1=q1.front();
q1.pop();
if(now1.dis>=9) return -1;
int x,y;
x=now1.pos/5;
y=now1.pos%5;
for(int i=0;i<8;i++)
{
int mx=x+f[i][0];
int my=y+f[i][1];
if(mx<0||mx>=5||my<0||my>=5) continue;
next1.pos=id[mx][my];
next1.dis=now1.dis+1;
next1.state=now1.state;
if(now1.state&(1<<id[mx][my]))
{
next1.state|=(1<<id[x][y]);
next1.state^=(1<<id[mx][my]);
}
p1=make_pair(next1.state,next1.pos);
if(m1.find(p1)==m1.end())
{
if(m2.find(p1)!=m2.end()) return next1.dis+m2[p1]-2;
m1[p1]=next1.dis;
q1.push(next1);
}
}
now2=q2.front();
q2.pop();
if(now2.dis>=8) return -1;
x=now2.pos/5;
y=now2.pos%5;
for(int i=0;i<8;i++)
{
int mx=x+f[i][0];
int my=y+f[i][1];
if(mx<0||mx>=5||my<0||my>=5) continue;
next2.pos=id[mx][my];
next2.dis=now2.dis+1;
next2.state=now2.state;
if(now2.state&(1<<id[mx][my]))
{
next2.state|=(1<<id[x][y]);
next2.state^=(1<<id[mx][my]);
}
p2=make_pair(next2.state,next2.pos);
if(m2.find(p2)==m2.end())
{
if(m1.find(p2)!=m1.end()) return next2.dis+m1[p2]-2;
m2[p2]=next2.dis;
q2.push(next2);
}
}
}
return -1;
}
int main()
{
int num=0;
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
id[i][j]=num++;
state1=0;
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
{
if(a[i][j]=='1') state1|=(1<<id[i][j]);
if(a[i][j]=='*') pos1=id[i][j];
}
int T;
scanf("%d",&T);
while(T--)
{
state2=0;
for(int i=0;i<5;i++)
{
scanf("%s",b[i]);
for(int j=0;j<5;j++)
{
if(b[i][j]=='1') state2|=(1<<id[i][j]);
if(b[i][j]=='*') pos2=id[i][j];
}
}
int res=bfs();
if(res==-1||res>15) puts("-1");
else printf("%d\n",res);
}
return 0;
}
nzhtl1477 @ 2018-01-09 09:52:34
[ Quote ] [ Edit ] [ Delete ] 2#
Claris也女装
EdwardFrog @ 2018-01-09 09:55:09
[ Quote ] [ Edit ] [ Delete ] 3#
I is fish
EdwardFrog @ 2018-01-09 09:55:25
[ Quote ] [ Edit ] [ Delete ] 4#
您好,为什么要强调您是女装呢
iloi @ 2018-01-09 11:06:04
[ Quote ] [ Edit ] [ Delete ] 5#
Cgays也女装
RabbitHu @ 2018-01-09 13:45:56
[ Quote ] [ Edit ] [ Delete ] 6#
我也是女装!
yycc @ 2018-01-09 17:58:18
[ Quote ] [ Edit ] [ Delete ] 7#
lkh也女装!
EdwardFrog @ 2018-01-09 19:56:43
[ Quote ] [ Edit ] [ Delete ] 8#
我也女装!
oscar2001 @ 2018-01-12 17:28:27
[ Quote ] [ Edit ] [ Delete ] 9#
myselves was yu
AC_test @ 2018-01-12 17:31:55
[ Quote ] [ Edit ] [ Delete ] 10#
人呐就都不知道,自己不可以预料。一个人的命运啊,当然要靠自我奋斗,但是也考虑到历史的进程。你说我一女装来提问,怎么就火了呢
Ivan @ 2018-01-14 21:00:28
[ Quote ] [ Edit ] [ Delete ] 11#
人呐就都不知道,自己就不可以预料。一个人的命运啊,当然要靠自我奋斗,但是也要考虑到历史的行程。
jmsyzsfq @ 2018-01-16 09:05:46
[ Quote ] [ Edit ] [ Delete ] 12#
人呐就都不知道,自己就不可以预料。一个人的命运啊,当然要靠自我奋斗,但是也要考虑到历史的行程。
YuhangQ @ 2018-01-17 11:16:00
[ Quote ] [ Edit ] [ Delete ] 13#
基佬省 yyc 也要女装!
YuhangQ @ 2018-01-17 11:16:23
[ Quote ] [ Edit ] [ Delete ] 14#
@yycc
nzhtl1477 @ 2018-01-17 11:18:55
[ Quote ] [ Edit ] [ Delete ] 15#
女装!
[Top] [Previous Page] [Next Page]

HOME Back