题解 - Vijos

2

PowderHan LV 10 @ 2016-10-30 23:09:50

一个dfs预处理出能打到女飞贼的位置，然后来一遍bfs，数组直接开一维来个ya()就好了

1

lk992969044 LV 7 @ 2018-11-09 08:48:18

数据很水不用预处理直接 bfs 最大的数据是 22ms

1

juan1973 LV 10 @ 2014-02-04 14:27:18

这是一个宽搜衍生出来的题目。
一开始WA了好几次，发现如下问题：
（1）Impossible打错了。
（2）飞镖无距离限制，只要不穿墙（P.S.我一开始不知道什么是重狙，才没发现，现在一想应该是一种枪吧）
（3）宽搜每次前要初始化。
为了加快速度，我们先做一个预处理，从女飞贼开始统计飞镖能达到的位置，用数组OK记录。
还有，m*n=20000，不能用二维，要转化后存储。

BY JSB 绍兴一中万岁！
#include<stdio.h>
using namespace std;
long f[20001];
long d[2][4]={{-1,0,0,1},{0,-1,1,0}};
long i,j,p,q,n,m,h,t,gox,goy,nowx,nowy,go,now,x1,y1,x2,y2,ans;
bool map[20001]={false};
long x[20001],y[20001],z[20001];
bool ok[20001];
long make(long x,long y)
{
if ((x<1)||(x>n)||(y<1)||(y>m)) return 0;
return (x-1)*m+y;
}
void yuchuli()
{
long nowx,nowy,x,y,p,q,put;
nowx=x1;nowy=y1;
ok[make(nowx,nowy)]=true;
for (p=-1;p<2;p++)
if (p!=0)
{
x=nowx+p;y=nowy;put=make(x,y);
while ((x>0)&&(x<=n)&&(map[put]))
{
ok[put]=true;
x+=p;
put=put+p*m;
}
x=nowx;y=nowy+p;put=make(x,y);
while ((y>0)&&(y<=m)&&(map[put]))
{
ok[put]=true;
y+=p;
put=put+p;
}
}
for (p=-1;p<2;p++)
for (q=-1;q<2;q++)
if ((p!=0)&&(q!=0))
{
x=nowx+p;y=nowy+q;
put=make(x,y);
while ((put>0)&&(put<=m*n)&&(map[put]))
{
ok[put]=true;
x+=p;y+=q;
put=make(x,y);
}
}
}
int main()
{
scanf("%ld %ld",&n,&m);
char hang,u;
scanf("%c",&hang);
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++)
{
scanf("%c",&u);
if (u=='O') map[make(i,j)]=true;
}
scanf("%c",&hang);
}
map[0]=false;
while (0==0)
{
scanf("%ld %ld %ld %ld",&x1,&y1,&x2,&y2);
if (x1+x2+y1+y2==0) break;
for (i=1;i<=20000;i++)
{
f[i]=20001;
ok[i]=false;
}
yuchuli();
ans=20001;
x[1]=x2;y[1]=y2;z[1]=make(x2,y2);f[z[1]]=0;
if (ok[z[1]]) ans=0;
h=0;t=1;
if (ans>0)
while (h<t)
{
h++;
nowx=x[h];nowy=y[h];
now=z[h];
for (i=0;i<=3;i++)
{
gox=nowx+d[0][i];goy=nowy+d[1][i];
go=make(gox,goy);
if (!map[go]) continue;
if (f[now]+1<f[go])
{
t++;x[t]=gox;y[t]=goy;z[t]=go;f[go]=f[now]+1;
if (ok[go]&&(f[go]<ans)) ans=f[go];
}
}
}
if (ans<20001) printf("%ld",ans);
else printf("Impossible!");
printf("\n");

}
return 0;
}

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 792 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 788 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 788 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 792 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 788 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 792 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 792 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 792 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 788 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 792 KiB, score = 10
Accepted, time = 15 ms, mem = 792 KiB, score = 100

0

Bill_Yang LV 10 @ 2017-02-15 00:25:35

暴力做法，无需解释

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int Dirx[]= {0,1,-1,0,0},Diry[]= {0,0,0,1,-1};
struct Sword {
int x,y,time;
Sword() {}
Sword(int _,int __,int ___):x(),y(),time(__) {}
bool operator < (const Sword& b) const {
return (x<b.x||y<b.y);
}
bool operator > (const Sword& b) const {
return (x>b.x||y>b.y);
}
} Start,End;
int n,m,vst[505][505];
char map[505][505];
bool Check(Sword Now,Sword Next) {
if(Now.x==Next.x) {
bool bj=1;
for(int i=min(Now.y,Next.y); i<=max(Now.y,Next.y); i++)
if(map[Now.x][i]=='X') {
bj=0;
break;
}
if(bj)return true;
}
if(Now.y==Next.y) {
bool bj=1;
for(int i=min(Now.x,Next.x); i<=max(Now.x,Next.x); i++)
if(map[i][Now.y]=='X') {
bj=0;
break;
}
if(bj)return true;
}
if(Now.x+Now.y==Next.x+Next.y) {
bool bj=1;
for(int i=min(Now.x,Next.x),j=max(Now.y,Next.y); i<=max(Now.x,Next.x)&&j>=min(Now.y,Next.y); i++,j--)
if(map[i][j]=='X') {
bj=0;
break;
}
if(bj)return true;
}
if(Now.x-Now.y==Next.x-Next.y) {
bool bj=1;
for(int i=min(Now.x,Next.x),j=min(Now.y,Next.y); i<=max(Now.x,Next.x)&&j<=max(Now.y,Next.y); i++,j++)
if(map[i][j]=='X') {
bj=0;
break;
}
if(bj)return true;
}
return false;
}
int Bfs(Sword Start,Sword End) {
queue<Sword>Q;
Q.push(Start);
memset(vst,0,sizeof(vst));
vst[Start.x][Start.y]=1;
while(!Q.empty()) {
Sword Now=Q.front();
Q.pop();
if(Check(Now,End))return Now.time;
for(int i=1; i<=4; i++) {
Sword Next=Sword(Now.x+Dirx[i],Now.y+Diry[i],Now.time+1);
if(map[Next.x][Next.y]=='X'||vst[Next.x][Next.y]||Next>Sword(n,m,0)||Next<Sword(1,1,0))continue;
vst[Next.x][Next.y]=1;
Q.push(Next);
}
}
return -1;
}
int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++)map[i][j]=getchar();
getchar();
}
while(true) {
cin>>End.x>>End.y>>Start.x>>Start.y;
if(Start.x==0&&Start.y==0&&End.x==0&&End.y==0)break;
int ans=Bfs(Start,End);
if(ans==-1)puts("Impossible!");
else printf("%d\n",ans);
}
return 0;
}

0

lrj124 LV 10 @ 2016-09-09 16:33:26

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 752 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 752 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 752 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 752 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 752 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 756 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 756 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 756 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 752 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 752 KiB, score = 10
Accepted, time = 0 ms, mem = 756 KiB, score = 100
代码
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;
const int X[] = {-1,-1,-1,0,0,1,1,1},Y[] = {-1,0,1,-1,1,-1,0,1},INT_MAX = 9999999;
struct coord {
  int x,y;
};
int n,m,x1,x2,Y1,y2,answer[201][201];
char map[201][201];
queue <coord> Q;
int main() {
  //freopen("thief.in","r",stdin);
  //freopen("thief.out","w",stdout);
  scanf("%d%d",&n,&m);
  for (int i = 1;i <= n;i++) scanf("%s",map[i]+1);
  while (scanf("%d%d%d%d",&x1,&Y1,&x2,&y2)) {
    if (!x1 && !Y1 && !x2 && !y2) break;
    int ans = INT_MAX;
    for (int i = 1;i <= n;i++)
      for (int j = 1;j <= m;j++)
        if (map[i][j] == 'X') answer[i][j] = -1;
        else if(map[i][j]=='O') answer[i][j] = INT_MAX;
    while (!Q.empty()) Q.pop();
    Q.push((coord){x2,y2});
    answer[x2][y2] = 0;
    while (!Q.empty()) {
      coord now = Q.front(); Q.pop();
      if (now.x+1 <= n && answer[now.x+1][now.y] != -1 && answer[now.x+1][now.y] == INT_MAX && (now.x+1 != x2 || now.y != y2)) {
        Q.push((coord){now.x+1,now.y});
        answer[now.x+1][now.y] = answer[now.x][now.y]+1;
      }
      if (now.y+1 <= m && answer[now.x][now.y+1] != -1 && answer[now.x][now.y+1] == INT_MAX && (now.x != x2 || now.y+1 != y2)) {
        Q.push((coord){now.x,now.y+1});
        answer[now.x][now.y+1] = answer[now.x][now.y]+1;
      }
      if (now.x-1 > 0 && answer[now.x-1][now.y] != -1 && answer[now.x-1][now.y] == INT_MAX && (now.x-1 != x2 || now.y != y2)) {
        Q.push((coord){now.x-1,now.y});
        answer[now.x-1][now.y] = answer[now.x][now.y]+1;
      }
      if (now.y-1 > 0 && answer[now.x][now.y-1] != -1 && answer[now.x][now.y-1] == INT_MAX && (now.x != x2 || now.y-1 != y2)) {
        Q.push((coord){now.x,now.y-1});
        answer[now.x][now.y-1] = answer[now.x][now.y]+1;
      }
    }
    for (int i = 0;i < 8;i++) {
      int x = x1+X[i],y = Y1+Y[i];
      while (answer[x][y] != -1 && x <= n && x > 0 && y <= m && y > 0) {
        ans = min(ans,answer[x][y]);
        x += X[i];
        y += Y[i];
      }
    }
    if (ans == INT_MAX)
      printf("Impossible!\n");
    else
      printf("%d\n",ans);
  }
  return 0;
}

0

吴佳泽 LV 8 @ 2016-08-02 09:41:20

(@ο@) 哇～
**
满满的回忆啊~~~~~~~~~~~~~~~~~~
感动ing
满满的回忆啊~~~~~~~~~~~~~~~~~~
**

hsez_woixia1314 @ 2016-08-03 15:37:43

yeah,I just can't do it.哈哈

0

151052 LV 9 @ 2016-02-02 20:02:44

卧槽，铜钱镖能飞八个方向！wa了三次啊！！！

0

dkax LV 8 @ 2016-02-02 09:55:42

咳，同学们，我啥都不说了，如果你的结果是70分的话，试试1 1 O 1 1 1 1这个数据吧，，，，WA了三次。。。。。。哭

0

一方T行 LV 10 @ 2014-10-28 00:08:44

飞贼与月如坐标打反WA了一次。。。

0

H<<H>>D LV 8 @ 2014-02-03 21:29:04

先预处理出能打到女飞贼的所有地方，然后从主角开始BFS
注意：飞镖的距离是无限的。由于题目只告诉了n*m,所以我直接把他们并在一排了
#include<stdio.h>
using namespace std;
bool map[200000],canheat[20001];
long x1,y1,x2,y2;
bool gone[200000];long que[50000],k[50000];bool endflag;long ans=0;
long n,m;
int main()
{
scanf("%ld%ld",&n,&m);char a;scanf("%c",&a); //一开始没注意到这个坑爹的换行符！坑了我好久！
for(long i=1;i<=n;i++)
{
for(long j=1;j<=m;j++){char s;scanf("%c",&s);if(s=='O')map[(i-1)*m+j]=true;else map[(i-1)*m+j]=false;}
char u;scanf("%c",&u);
}
while(true)
{
scanf("%ld%ld%ld%ld",&x1,&y1,&x2,&y2);
if(x1==0&&x2==0&&y1==0&&y2==0)break;
for(long i=1;i<=n;i++)for(long j=1;j<=m;j++)canheat[(i-1)*m+j]=-1;
canheat[(x1-1)*m+y1]=0;long x,y;
//for(long i=1;i<=n;i++){for(long j=1;j<=m;j++)printf("%ld ",map[(i-1)*m+j]?0:1);printf("\n");}
x=x1;while(x+1<=n&&map[x*m+y1]==true){x++;canheat[(x-1)*m+y1]=0;}
x=x1;while(x-1>=1&&map[(x-2)*m+y1]==true){x--;canheat[(x-1)*m+y1]=0;}
y=y1;while(y+1<=m&&map[(x1-1)*m+y+1]==true){y++;canheat[(x1-1)*m+y]=0;}
y=y1;while(y-1>=1&&map[(x1-1)*m+y-1]==true){y--;canheat[(x1-1)*m+y]=0;}
x=x1;y=y1;while(x+1<=n&&y+1<=m&&map[x*m+y+1]==true){x++;y++;canheat[(x-1)*m+y]=0;}
x=x1;y=y1;while(y-1>=1&&x+1<=n&&map[x*m+y-1]==true){x++;y--;canheat[(x-1)*m+y]=0;}
x=x1;y=y1;while(x-1>=1&&y-1>=1&&map[(x-2)*m+y-1]==true){x--;y--;canheat[(x-1)*m+y]=0;}
x=x1;y=y1;while(x-1>=1&&y+1<=m&&map[(x-2)*m+y+1]==true){x--;y++;canheat[(x-1)*m+y]=0;}
if(canheat[(x2-1)*m+y2]==0)printf("0\n");
else
{
for(long i=1;i<=n*m;i++)gone[i]=false;gone[(x2-1)*m+y2]=true;que[0]=1;que[1]=(x2-1)*m+y2;endflag=false;ans=0;
while(que[0]!=0&&endflag==false)
{
k[0]=0;
for(long i=1;i<=que[0];i++)
{
long cur=que[i];if(canheat[cur]==0&&endflag==false){printf("%ld\n",ans);endflag=true;}x=cur/m+1;y=cur%m;
if(y==0){y=m;x--;}
//printf("now king %ld %ld\n",x,y);
if(x+1<=n&&map[x*m+y]==true&&gone[x*m+y]==false){k[0]++;k[k[0]]=x*m+y;gone[x*m+y]=true;}
if(y+1<=m&&map[(x-1)*m+y+1]==true&&gone[(x-1)*m+y+1]==false){k[0]++;k[k[0]]=(x-1)*m+y+1;gone[(x-1)*m+y+1]=true;}
if(x-1>=1&&map[(x-2)*m+y]==true&&gone[(x-2)*m+y]==false){k[0]++;k[k[0]]=(x-2)*m+y;gone[(x-2)*m+y]=true;}
if(y-1>=1&&map[(x-1)*m+y-1]==true&&gone[(x-1)*m+y-1]==false){k[0]++;k[k[0]]=(x-1)*m+y-1;gone[(x-1)*m+y-1]=true;}
}
que[0]=k[0];for(long i=1;i<=k[0];i++)
que[i]=k[i];
//printf("%ld %ld\n",que[i]/m+1,que[i]%m);}
ans++;
}
if(!endflag)printf("Impossible!\n");
}
}
return 0;
}

0

玛维-影之歌 LV 10 @ 2009-10-07 16:06:34

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

無語......開個數組記錄有沒有走到過當前點...結果第一次忘了用了...10分

暴力BFS...啥優化都不要..0MS..

0

db_db_Jacky LV 10 @ 2009-10-07 00:28:39

诡异。。1次80分。。费解了~~

极度萎缩的复制了8遍

for i:=1 to x0-1 do

if map[x0-i,y0]

then yue[x0-i,y0]:=true

else break;

for i:=1 to n-x0 do

if map[x0+i,y0]

then yue[x0+i,y0]:=true

else break;

for i:=1 to y0-1 do

if map[x0,y0-i]

then yue[x0,y0-i]:=true

else break;

for i:=1 to m-y0 do

if map[x0,y0+i]

then yue[x0,y0+i]:=true

else break;

for i:=1 to x0-1 do

if map[x0-i,y0-i]

then yue[x0-i,y0-i]:=true

else break;

for i:=1 to n-x0 do

if map[x0+i,y0-i]

then yue[x0+i,y0-i]:=true

else break;

for i:=1 to y0-1 do

if map[x0-i,y0+i]

then yue[x0-i,y0+i]:=true

else break;

for i:=1 to m-y0 do

if map[x0+i,y0+i]

then yue[x0+i,y0+i]:=true

else break;

0

kivenzhang LV 8 @ 2009-09-01 17:03:14

靠先是女飞贼再是林月如的位置啊！！！！！！！！！！！

0

fenghao LV 10 @ 2009-08-22 00:19:23

挺无聊的题目。。

适合kill time。。

不知道其他人怎么样。。反正我是写了84行。。感觉挺多的。。

注意判断击中的情况，是在一条直线上而不是紧挨着。。

其他的题目怎么说就怎么做了。。

不知道数据是什么。。不过我200*200的数组过了。。

0

gaoji7777 LV 10 @ 2009-08-20 18:35:27

靠!以为主角肯定在前面输入的.......

0

LP.Fighting LV 10 @ 2009-08-20 22:27:52

所有重复用到的变量一定要初始化!!!!!!!!!!!!!

WA了3次的教训...

说明静态查错是很重要的...

0

brace_123 LV 9 @ 2009-07-30 17:08:07

BFS

基础题

0

mike_nzk LV 10 @ 2009-07-09 16:29:01

宽搜，还加了1个小优化，全部秒杀。

0

sdfasf LV 10 @ 2009-07-05 23:28:29

怎么一片128?

0

怪盗~基德 LV 10 @ 2009-05-26 11:07:07

二维数组估计要爆，限制是n*m

ljhzlh @ 2013-12-24 13:12:38

二维数组不会爆，反正我用CPP是没爆的。

题解

69 条题解

单挑女飞贼

信息

状态

开发

支持

题解

69 条题解

单挑女飞贼

信息

状态

开发

支持

还没有账户？

登录