27 条题解
-
1
aph。 (chenqianrong) LV 10 @ 2021-09-04 19:53:22
#include <bits/stdc++.h> using namespace std; bool a[55][55]; bool aa[55][55][4]; int b[10000][4]; int n,m,x,y,xx,yy; int step=1,flag=0; char c; int frot=0,rear=1; int turn(int u, bool lr) { if(lr==0){ if(u==0) return 3; else return u-1; } else{ if(u==3) return 0; else return u+1; } } void bfs() { int i,x,y,d,step; while(frot<rear){ x=b[frot][0],y=b[frot][1],d=b[frot][2],step=b[frot][3]; if(x==xx && y==yy){ cout<<b[frot][3]; return; } if(aa[x][y][turn(d,0)]==0){ aa[x][y][turn(d,0)]=1; b[rear][0]=x; b[rear][1]=y; b[rear][2]=turn(d,0); b[rear++][3]=step+1; } if(aa[x][y][turn(d,1)]==0){ aa[x][y][turn(d,1)]=1; b[rear][0]=x; b[rear][1]=y; b[rear][2]=turn(d,1); b[rear++][3]=step+1; } for(i=1; i<=3; i++){ if(d==0 && aa[x-i][y][d]==0 && a[x-1][y]==0 && a[x-i][y]==0 && x-i>0){ aa[x-i][y][d]=1; b[rear][0]=x-i; b[rear][1]=y; b[rear][2]=d; b[rear++][3]=step+1; } if(d==2 && aa[x+i][y][d]==0 && a[x+1][y]==0 && a[x+i][y]==0 && x+i<n){ aa[x+i][y][d]=1; b[rear][0]=x+i; b[rear][1]=y; b[rear][2]=d; b[rear++][3]=step+1; } if(d==3 && aa[x][y-i][d]==0 && a[x][y-1]==0 && a[x][y-i]==0 && y-i>0){ aa[x][y-i][d]=1; b[rear][0]=x; b[rear][1]=y-i; b[rear][2]=d; b[rear++][3]=step+1; } if(d==1 && aa[x][y+i][d]==0 && a[x][y+1]==0 && a[x][y+i]==0 && y+i<m){ aa[x][y+i][d]=1; b[rear][0]=x; b[rear][1]=y+i; b[rear][2]=d; b[rear++][3]=step+1; } } frot++; } cout << -1; } int main() { int i,j,d,t; cin>>n>>m; for(i=1; i<=n; i++) for(j=1; j<=m; j++){ cin>>t; if(t==1) a[i][j]=a[i-1][j]=a[i][j-1]=a[i-1][j-1]=1; } cin>>x>>y>>xx>>yy>>c; if(c=='N') d=0; else if(c=='E') d=1; else if(c=='S') d=2; else d=3; aa[x][y][d]=1; b[0][0]=x,b[0][1]=y,b[0][2]=d,b[0][3]=0; bfs(); return 0; } -
1
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
int x,y,d,step;
}que[1110000];
bool visit[60][60][4];
int head,tail,dir;
int map[60][60],data[60][60];
int sx,sy,ex,ey,n,m;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
int bfs()
{
if(map[sx][sy] || map[ex][ey])return -1;
if(sx==ex && sy==ey)return 0;
head=tail=1;
que[1].x=sx,que[1].y=sy,que[1].d=dir,que[1].step=0;
visit[sx][sy][dir]=0;
while(head<=tail)
{
node now=que[head++];
node next;
for(int i=1;i<=3;i++)
{
next=now;
next.x+=dx[now.d]*i;
next.y+=dy[now.d]*i;
next.step++;
if(next.x<1 || next.y<1 || next.x>n || next.y>m)break;
if(map[next.x][next.y])break;
if(!visit[next.x][next.y][next.d])
{
visit[next.x][next.y][next.d]=1;
que[++tail]=next;
if(next.x==ex && next.y==ey)return next.step;
}
}
next=now;
next.step++;
next.d=(next.d+1)%4;
if(!visit[next.x][next.y][next.d])
{
visit[next.x][next.y][next.d]=1;
que[++tail]=next;
if(next.x==ex && next.y==ey)return next.step; next.step;
}
next=now;
next.step++;
next.d=(next.d+3)%4;
if(!visit[next.x][next.y][next.d])
{
visit[next.x][next.y][next.d]=1;
que[++tail]=next;
if(next.x==ex && next.y==ey)return next.step;
}
}
return -1;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&data[i][j]);
}
}
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
char ch;
scanf("%c",&ch);
scanf("%c",&ch);
if(ch=='N') dir=0;
else if(ch=='E') dir=1;
else if(ch=='S') dir=2;
else dir=3;
n--; m--;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(data[i][j] || data[i+1][j] || data[i][j+1] || data[i+1][j+1])
map[i][j]=1;
else map[i][j]=0;
}
}
int ans=bfs();
printf("%d\n",ans);
return 0;
} -
0
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
int x,y,d,step;
}que[110000];
int head,tail,dir;
bool visit[60][60][4];
int map[60][60],data[60][60];
int sx,sy,ex,ey,n,m;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
int bfs()
{
if(map[sx][sy]||map[ex][ey]) return -1;
if(sx==ex && sy==ey) return 0;
head=tail=1;
que[1].x=sx,que[1].y=sy,que[1].d=dir,que[1].step=0;
visit[sx][sy][dir]=0;
while(head<=tail)
{
node now=que[head++];
node next;
for(int i=1;i<=3;i++)
{
next=now;
next.x+=dx[now.d]i;
next.y+=dy[now.d]i;
next.step++;
if(next.x<1 || next.y<1 || next.x>n || next.y>m) break;
if(map[next.x][next.y]) break;
if(!visit[next.x][next.y][next.d])
{
visit[next.x][next.y][next.d]=1;
que[++tail]=next;
if(next.x== ex && next.y==ey) return next.step;
}
}
next=now;
next.step++;
next.d=(next.d+1)%4;
if(!visit[next.x][next.y][next.d])
{
visit[next.x][next.y][next.d]=1;
que[++tail]=next;
if(next.x== ex && next.y==ey) return next.step;
}
next=now;
next.step++;
next.d=(next.d+3)%4;
if(!visit[next.x][next.y][next.d])
{
visit[next.x][next.y][next.d]=1;
que[++tail]=next;
if(next.x== ex && next.y==ey) return next.step;
}
}
return -1;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&data[i][j]);
}
}
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
char ch;
scanf("%c",&ch);
scanf("%c",&ch);
if(ch=='N') dir=0;
else if(ch=='E') dir=1;
else if(ch=='S') dir=2;
else dir=3;
n--; m--;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(data[i][j] || data[i+1][j] || data[i][j+1] || data[i+1][j+1])
map[i][j]=1;
else map[i][j]=0;
}
}
int ans=bfs();
printf("%d\n",ans);
return 0;
} -
0
评测结果
编译成功测试数据 #0: Accepted, time = 3 ms, mem = 2248 KiB, score = 10
测试数据 #1: Accepted, time = 1 ms, mem = 2248 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 2252 KiB, score = 10
测试数据 #3: Accepted, time = 4 ms, mem = 2248 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 2252 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 2252 KiB, score = 10
测试数据 #6: Accepted, time = 1 ms, mem = 2252 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 2252 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 2248 KiB, score = 10
测试数据 #9: Accepted, time = 34 ms, mem = 2252 KiB, score = 10
Accepted, time = 58 ms, mem = 2252 KiB, score = 100
代码
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
int x,y,d,step;
}que[110000];
int head,tail,dir;
bool visit[60][60][4];
int map[60][60],data[60][60];
int sx,sy,ex,ey,n,m;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
int bfs()
{
if(map[sx][sy]||map[ex][ey]) return -1;
if(sx==ex && sy==ey) return 0;
head=tail=1;
que[1].x=sx,que[1].y=sy,que[1].d=dir,que[1].step=0;
visit[sx][sy][dir]=0;
while(head<=tail)
{
node now=que[head++];
node next;
for(int i=1;i<=3;i++)
{
next=now;
next.x+=dx[now.d]*i;
next.y+=dy[now.d]*i;
next.step++;
if(next.x<1 || next.y<1 || next.x>n || next.y>m) break;
if(map[next.x][next.y]) break;
if(!visit[next.x][next.y][next.d])
{
visit[next.x][next.y][next.d]=1;
que[++tail]=next;
if(next.x== ex && next.y==ey) return next.step;
}
}
next=now;
next.step++;
next.d=(next.d+1)%4;
if(!visit[next.x][next.y][next.d])
{
visit[next.x][next.y][next.d]=1;
que[++tail]=next;
if(next.x== ex && next.y==ey) return next.step;
}
next=now;
next.step++;
next.d=(next.d+3)%4;
if(!visit[next.x][next.y][next.d])
{
visit[next.x][next.y][next.d]=1;
que[++tail]=next;
if(next.x== ex && next.y==ey) return next.step;
}}
return -1;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&data[i][j]);
}
}
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
char ch;
scanf("%c",&ch);
scanf("%c",&ch);
if(ch=='N') dir=0;
else if(ch=='E') dir=1;
else if(ch=='S') dir=2;
else dir=3;
n--; m--;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(data[i][j] || data[i+1][j] || data[i][j+1] || data[i+1][j+1])
map[i][j]=1;
else map[i][j]=0;
}
}
int ans=bfs();
printf("%d\n",ans);
return 0;
} -
0
评测结果
编译成功测试数据 #0: Accepted, time = 0 ms, mem = 3704 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 3740 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 3740 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 3740 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 3740 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 3740 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 3744 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 3740 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 3740 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 3740 KiB, score = 10
Accepted, time = 15 ms, mem = 3744 KiB, score = 100
代码
program rm;
type num=record
x,y,w:longint;
end;
var vv:array[0..101,0..101]of boolean;
b:array[0..101,0..101]of integer;
a:array[0..200001]of num;
q:array[0..50001]of longint;
star:array[0..50001]of longint;
d:array[0..50001]of longint;
n,mm,i,j,k,s,t,sx,sy,tx,ty,kk,st,ed,m,ans:longint;
c,ch:char;
procedure duru(x0,y0,xx,yy,kt:longint);
var i,j:longint;
begin
j:=x0*300+5*y0+kt;
i:=xx*300+5*yy+kt;
inc(mm);
a[mm].x:=j;
a[mm].y:=i;
a[mm].w:=1;
end;
procedure work0(x,y:longint);
var i,j:longint;
begin
i:=x; j:=y;
if (j-1>=1)and(vv[i,j-1]) then
begin
duru(i,j,i,j-1,0);
if (j-2>=1)and(vv[i,j-2]) then
begin
duru(i,j,i,j-2,0);
if (j-3>=1)and(vv[i,j-3])then
duru(i,j,i,j-3,0);
end;
end;
end;
procedure work1(x,y:longint);
var i,j:longint;
begin
i:=x; j:=y;
if (i-1>=1)and(vv[i-1,j-1]) then
begin
duru(i,j,i-1,j,1);
if (i-2>=1)and(vv[i-2,j-2]) then
begin
duru(i,j,i-2,j,1);
if (i-3>=1)and(vv[i-3,j-3])then
duru(i,j,i-3,j,1);
end;
end;
end;
procedure work2(x,y:longint);
var i,j:longint;
begin
i:=x; j:=y;
if (j+1<=m-1)and(vv[i,j+1]) then
begin
duru(i,j,i,j+1,2);
if (j+2<=m-1)and(vv[i,j+2]) then
begin
duru(i,j,i,j+2,2);
if (j+3<=m-1)and(vv[i,j+3])then
duru(i,j,i,j+3,2);
end;
end;
end;
procedure work3(x,y:longint);
var i,j:longint;
begin
i:=x; j:=y;
if (i+1<=n-1)and(vv[i+1,j]) then
begin
duru(i,j,i+1,j,3);
if (i+2<=n-1)and(vv[i+2,j]) then
begin
duru(i,j,i+2,j,3);
if (i+3<=n-1)and(vv[i+3,j])then
duru(i,j,i+3,j,3);
end;
end;
end;
procedure doing;
var i,j,t:longint;
begin
for i:=1 to n-1 do
for j:=1 to m-1 do
for k:=0 to 3 do
if vv[i,j] then
begin
t:=300*i+5*j+k;
inc(mm);a[mm].x:=t;
a[mm].y:=t-k+(k+1)mod 4;
a[mm].w:=1;
inc(mm);a[mm].y:=t;
a[mm].x:=t-k+(k+1)mod 4;
a[mm].w:=1;
inc(mm);a[mm].x:=t;
a[mm].y:=t-k+(k+3)mod 4;
a[mm].w:=1;
inc(mm);a[mm].y:=t;
a[mm].x:=t-k+(k+3)mod 4;
a[mm].w:=1;
if k=0 then work0(i,j);
if k=1 then work1(i,j);
if k=2 then work2(i,j);
if k=3 then work3(i,j);
end;
end;
procedure kp(s,t:longint);
var i,j:longint; tt,te:num;
begin
i:=s; j:=t;
te:=a[(s+t)>>1];
while i<j do
begin
while a[i].x<te.x do inc(i);
while a[j].x>te.x do dec(j);
if i<=j then
begin
tt:=a[i]; a[i]:=a[j];a[j]:=tt;
inc(i);dec(j);
end;
end;
if j>s then kp(s,j);
if i<t then kp(i,t);
end;
procedure spfa;
var v:array[0..50001]of boolean;
i,u,now:longint;
begin
u:=50000;
st:=0; ed:=1;
q[1]:=s;
fillchar(v,sizeof(v),false);
for i:=1 to 300*n+5*m+3 do
d[i]:=maxlongint;
d[s]:=0; v[s]:=true;
while st<>ed do
begin
st:=st mod u +1;
now:=q[st];
i:=star[now];
while a[i].x=now do
begin
if d[a[i].x]+a[i].w<d[a[i].y] then
begin
d[a[i].y]:=d[a[i].x]+a[i].w;
if not v[a[i].y] then
begin
ed:=ed mod u+1;
q[ed]:=a[i].y;
v[a[i].y]:=true;
end;
end;
inc(i);
end;
v[now]:=false;
end;
end;
begin{main}
readln(n,m);
for i:=1 to n do
for j:=1 to m do
read(b[i,j]);
for i:=1 to n do
for j:=1 to m do
vv[i,j]:=false;
for i:=1 to n-1 do
for j:=1 to m-1 do
if (b[i,j]=0)and(b[i,j+1]=0)and(b[i+1,j]=0)and(b[i+1,j+1]=0)then
vv[i,j]:=true;
readln(sx,sy,tx,ty,c,ch);
if ch='E' then kk:=2;
if ch='S' then kk:=3;
if ch='W' then kk:=0;
if ch='N' then kk:=1;
if (not vv[sx,sy])or (not vv[tx,ty])then
begin
writeln(-1);
halt;
end;
s:=300*sx+5*sy+kk;
mm:=0;
doing;
kp(1,mm);
star[a[1].x]:=1;
for i:=2 to mm do
if a[i].x<>a[i-1].x then
star[a[i].x]:=i;
spfa;
t:=300*tx+5*ty; ans:=maxlongint;
for i:=0 to 3 do
if d[t+i]<ans then
ans:=d[t+i];
if ans=maxlongint then
writeln(-1)else writeln(ans);
end. -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms数组一定要开得大啊．．．．
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 509ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：509ms原来结果可以为0！
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms热烈庆祝AC100题！！！NOIP2008即将到来！加油加油加油！
-
0
老師給咱看這道題的時候有一張很標準的圖，咱上傳了，這裡，給沒看過的同學少走彎路吧。
http://images.blogcn.com//2008/11/3/11/sykefelix,20081103113534583.png
看到這種“矩陣地圖上到處亂走”的題，大家通常首先想到的都是搜索吧，而且求“最短時間”，顯然Depth First不容易達到要求。
然而本題很陰險：“机器人的形状是一个直径1.6米的球”。
而且“机器人的中心总是在格点上”。
這樣就是指，機器人是會佔用掉2x2的位置的...所以很明顯，原先的地圖需要修改一下，改成咱們平常習慣的地圖。這也就是樓下下...下ipip2005牛的思路。這裡詳細説明一下，以咱的樣例為例：
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0機器人是站在“格點”，而矩陣中數字表示“格”，所以創建新矩陣Map[n+1, m+1]，遍歷原矩陣OrgMap每一個格點也就是四個數字的中心位置，只要該格點周圍的數字中有1，則該格點不可到達，在Map中標記為1。
周圍都是0自然就是0咯。然後把新矩陣加上1的邊框，方便寬搜判斷。
這樣，新矩陣的大小行列恰好比原矩陣多1，所以是Map[n+1, m+1]。
代碼不貼了，一來很簡單，二來怕被刪。建立好的新矩陣為：
1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 1 1 1 1 1
1 0 0 1 1 0 0 0 1 1 1
1 0 1 1 1 0 0 0 0 0 1
1 0 1 1 0 0 1 1 0 0 1
1 0 0 0 0 1 1 1 0 0 1
1 0 0 1 1 1 1 0 0 0 1
1 0 0 1 1 1 0 0 0 0 1
1 1 0 0 0 0 0 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1然後寬搜就是了...
每一步動作可以是左轉，右轉，進一，進二，進三。很顯然進一不能就無法進二了，這個用For配合Break就好了。...對了，第4個測試點根本不用走哦。
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
题意不清,浪费一次提交,写的很辛苦,4KB,累~
aph。 (chenqianrong)
LV 10
@ 2021-09-04 19:53:22
