F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:祝各位Oier新年快乐,Rp++!
大视野在线测评-欢迎您
[ New Thread ]
Problem 1085 >> 我是女生刚学搜索没超时wa了有人能看看吗
mz_yyc @ 2018-01-06 10:26:34
[ 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;
}
dreamy_meIody @ 2018-01-06 11:24:25
[ Quote ] [ Edit ] [ Delete ] 2#
您好,为什么要强调您是女生呢
Cydiater @ 2018-01-06 14:17:01
[ Quote ] [ Edit ] [ Delete ] 3#
I is fish
iloi @ 2018-01-06 16:28:43
[ Quote ] [ Edit ] [ Delete ] 4#
I are fish too
EdwardFrog @ 2018-01-06 16:31:27
[ Quote ] [ Edit ] [ Delete ] 5#
Fish am me
Kemoto @ 2018-01-07 11:16:26
[ Quote ] [ Edit ] [ Delete ] 6#
您好,为什么要强调您是女生呢
nzhtl1477 @ 2018-01-07 14:33:46
[ Quote ] [ Edit ] [ Delete ] 7#
我也是女生!
yycc @ 2018-01-07 14:52:52
[ Quote ] [ Edit ] [ Delete ] 8#
We is fish
NiroBC @ 2018-01-07 15:58:09
[ Quote ] [ Edit ] [ Delete ] 9#
我很鄙视那种强调自己是女生为获得偏爱的人哦。自力更生吧。
Hallmeow @ 2018-01-07 16:28:59
[ Quote ] [ Edit ] [ Delete ] 10#
emmm我点进来看看评论而已233
callG @ 2018-01-07 17:51:00
[ Quote ] [ Edit ] [ Delete ] 11#
Fish is myself
yycc @ 2018-01-07 19:26:02
[ Quote ] [ Edit ] [ Delete ] 12#
I am xian fish.
strangers @ 2018-01-07 22:26:03
[ Quote ] [ Edit ] [ Delete ] 13#
要火的感觉啊....那就赶紧火钳留名喽
其实我也是女生!
stl @ 2018-01-07 22:36:13
[ Quote ] [ Edit ] [ Delete ] 14#
这真的不是在钓鱼吗
EdwardFrog @ 2018-01-08 10:36:08
[ Quote ] [ Edit ] [ Delete ] 15#
人呐就都不知道,自己不可以预料。一个人的命运啊,当然要靠自我奋斗,但是也考虑到历史的进程。你说我一个女生来提问,怎么就火了呢
yycc @ 2018-01-08 10:38:22
[ Quote ] [ Edit ] [ Delete ] 16#
玛里()斯
27rabbit @ 2018-01-08 17:28:45
[ Quote ] [ Edit ] [ Delete ] 17#
哎,钓鱼
tianfuzhen @ 2018-01-08 19:05:22
[ Quote ] [ Edit ] [ Delete ] 18#
钩直饵咸
cmd2001 @ 2018-01-08 20:43:37
[ Quote ] [ Edit ] [ Delete ] 19#
后排提醒这个号没有提交记录。
fish am we.
EdwardFrog @ 2018-01-08 20:52:29
[ Quote ] [ Edit ] [ Delete ] 20#
hot了诶...
Nikolai @ 2018-01-09 10:41:09
[ Quote ] [ Edit ] [ Delete ] 21#
那是我的错吗?女人没有幽默感。
RE_test @ 2018-01-09 18:03:53
[ Quote ] [ Edit ] [ Delete ] 22#
mine was yues
Mychael @ 2018-01-10 12:53:17
[ Quote ] [ Edit ] [ Delete ] 23#
没有提交记录。这。。。
OwenOwl @ 2018-01-10 13:15:05
[ Quote ] [ Edit ] [ Delete ] 24#
我是女生刚打蓝月没钱冲掉不出神戒有人能看看吗
EdwardFrog @ 2018-01-10 14:42:53
[ Quote ] [ Edit ] [ Delete ] 25#
我系渣渣辉,你充钱吧
jjikkollp @ 2018-01-10 22:53:51
[ Quote ] [ Edit ] [ Delete ] 26#
是不是大家都是点进来看评论的啊23333
hurry @ 2018-01-14 11:47:54
[ Quote ] [ Edit ] [ Delete ] 27#
火贴前排留名。
zP1nG @ 2018-01-16 08:57:07
[ Quote ] [ Edit ] [ Delete ] 28#
目测要火,火钳刘明QAQ
快让大家认识我,我在前排,我是zP1nG!!!
ldxxx @ 2018-01-16 08:58:08
[ Quote ] [ Edit ] [ Delete ] 29#
火钳刘明+1
Ps:zP1nG is SB
zP1nG @ 2018-01-16 08:59:11
[ Quote ] [ Edit ] [ Delete ] 30#
LS也是女生,但她就比LZ自力更生,还会喷人。
jmsyzsfq @ 2018-01-16 09:02:25
[ Quote ] [ Edit ] [ Delete ] 31#
我觉得也是
jyzlzh @ 2018-01-16 09:03:37
[ Quote ] [ Edit ] [ Delete ] 32#
mdzz,jy四人组我觉得也是
l1ll5 @ 2018-01-17 11:22:38
[ Quote ] [ Edit ] [ Delete ] 33#
我也要火~
大家认识我我是l1ll5!!!
l1II5 @ 2018-01-17 12:35:35
[ Quote ] [ Edit ] [ Delete ] 34#
我也要火~
大家认识我我是l1II5!!!
dreamy_meIody @ 2018-01-17 12:42:15
[ Quote ] [ Edit ] [ Delete ] 35#
我也要火~
大家认识我我是dreamy_meIody!!!
dreamy_melody @ 2018-01-17 13:39:32
[ Quote ] [ Edit ] [ Delete ] 36#
楼上已经具备了进集训队的一个条件
fake~
EdwardFrog @ 2018-01-17 13:56:22
[ Quote ] [ Edit ] [ Delete ] 37#
我也要火~
大家认识我我是EdwardFrog!!!
wangzhanpeng @ 2018-01-18 14:01:25
[ Quote ] [ Edit ] [ Delete ] 38#
火钳刘明
Duan2 @ 2018-01-19 19:22:33
[ Quote ] [ Edit ] [ Delete ] 39#
我也要火~
大家认识我我是Duan2baka!!!
弱省最弱OIer!!!
Ez3real @ 2018-01-19 20:04:56
[ Quote ] [ Edit ] [ Delete ] 40#
%%%NiroBC
GXZlegend @ 2018-01-20 14:47:48
[ Quote ] [ Edit ] [ Delete ] 41#
代码明显有问题,你本机是怎么A的。。
Cydiater @ 2018-01-23 22:08:13
[ Quote ] [ Edit ] [ Delete ] 42#
抱歉发上来才发现木有缩进。。。本机我确实是运行通过答案对的啊。。。有问题烦请明示。。。
我的思路是将X,Y的具体位置数值转换为下标a,b,先假设骑士没有空缺,用TF函数判定是否直接为F,没有的话再用maybe函数判定位置是否连续,不连续的话判为maybe连续判T;他给的样例输入我本机输出答案是对的,VS2010编译器。。。
当然你要吐槽我是“C风格的C++”。。。这。。。
wang_sj @ 2018-01-23 22:14:11
[ Quote ] [ Edit ] [ Delete ] 43#
厉害了!
yycc @ 2018-01-24 08:26:03
[ Quote ] [ Edit ] [ Delete ] 44#
原来你的逻辑是样例过了就是A了啊。。。自己看看原题数据范围。。。再不懂就别做了吧 = =+
EdwardForg @ 2018-01-24 14:51:44
[ Quote ] [ Edit ] [ Delete ] 45#
最后吐槽一句。。puts("7\n-1"),他给的样例输入我本机输出答案是对的啊。。。为什么交上来WA了呢。。
GXZlegend @ 2018-01-24 14:52:55
[ Quote ] [ Edit ] [ Delete ] 46#
@EdwardFrog
数据范围的话数组大小我试过用50000,变量我能想到的只有long int也不行所以上面程序才用的int和a[10][10];
我整个程序虽然现在无法AC但逻辑并没有错,我诚心诚意地发问了,你不说也就算了,用个puts吐槽我又是要作甚?
iloi @ 2018-01-24 20:31:54
[ Quote ] [ Edit ] [ Delete ] 47#
后排orz复刻帖
Saramanda @ 2018-01-24 21:05:05
[ Quote ] [ Edit ] [ Delete ] 48#
火钳刘明
Saramanda @ 2018-01-24 21:06:27
[ Quote ] [ Edit ] [ Delete ] 49#
突然发现此贴和http://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=1108 对话风格一致
cnlarryzhong @ 2018-01-24 21:36:39
[ Quote ] [ Edit ] [ Delete ] 50#
@Saramanda
不是我BS,他说的那种puts那叫性质恶劣,你可以指责我的代码,但你不能嘲讽我的诚心。。。
至于你说搜索的正确性。。。实话说,我没学过;但是就这题,我给出的这个答案而言,我并没有用到搜索的正确性的知识;如果我这个程序在逻辑上有考虑不周或者错误的地方,烦请指出,感激不尽;
我在这里发帖,只是想请教下我错在哪里导致无法AC而已。。。
[Top] [Previous Page] [Next Page]

HOME Back