机器人大盗 RoboThieves
田镜
原出处在这里：DMOJ - CCC '18 S3
这似乎是一个有些冷门的oj。。。
先是看一下题目（翻译后）：
题目背景
机器人Robo在一个工厂里，偷了很多东西现在要逃出去。
惊了为什么我自己程序跑的数据WA了QAQ2333
题目描述
把工厂看为一个n行m列字符矩阵。
工厂的出口可能在任意一个空地（用 . 表示）上，所以Robo要走所有的空地。Robo从S出发。可能有墙（用W表示），摄像机（用C表示），传送带。
摄像机可以拍到它所在行和所在列的状况（但不能穿墙），Robo不能出现在摄像机视线范围中，否则就挂了。
Robo不能穿墙，摄像机也不行。Robo只能上下左右移动。
传送带有4种：L，R，U，D（左右上下），可能有连续传送带，但Robo也可能被永远卡在传送带上?。传送带比地面高，所以在上面不会被拍到，但是传送带挡不住摄像机视线。
现在请求出，Robo到每个空地的最短步数，传送带上不算，如不能到达，输出-1。
输入输出格式
输入格式：
输入两个正整数n,m。
下面n行每行m个字符。
输出格式：
K行（K表示空地数），每行一个整数表示S到那个点Robo需要的最短步数（不能走到输出-1），输出按空地顺序（行优先，再列）
对于此题有非常显然的做法：DFS/BFS，然后我脑抽了竟然用了Dijkstra。。。为的就是懒得判环了。。。
但这种做法是十分危险的，一定要谨慎：
1.代码长，方法暴力不好看 （不过看起来倒是很直观）
2.空间耗得大（不过此题不会MLE）
3.不用堆优化的话时间慢（我还真没用。。。）不过这个oj速度比较快可以AC。（要是是CCF的老爷机绝对要挂）
有几个我差点被坑到的地方：我把摄像机视线全设为墙，但我后来摄像机视线又不能穿墙，导致有地方没有挡到；还有输出点的时候应该输出.的地方不是从第一个点开始。。。
先看容易看懂十分暴力不优美的Dijkstra：（真是丧心病狂）
做好看200+行代码准备：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int INF=0x7fffffff;
struct edge
{
int to,cost;
};
int fx[4]={1,0,-1,0};
int fy[4]={0,1,0,-1};
int row,col,d[10001],vis[10001],n,spot[10001],count_;
char a[101][101];
bool visit[10001][10001];
vector<edge> graph[10001];
void dijkstra(int s)
{
int min1,k;
for(int i=1;i<=row*col;i++)
d[i]=INF;
d[s]=0;
for(int i=1;i<row*col;i++)
{
min1=INF;
k=s;
for(int j=1;j<=row*col;j++)
if(!vis[j] && min1>d[j])
min1=d[j],k=j;
vis[k]=1;
for(int j=0;j<graph[k].size();j++)
{
int t=graph[k][j].to;
if(!vis[t] && min1+graph[k][j].cost<d[t])
d[t]=min1+graph[k][j].cost;
}
}
return;
}
int main()
{
// freopen("robothief010.in","r",stdin);
// freopen("robothief010.out","w",stdout);
bool flag=true;
int s;
cin>>row>>col;
for(int i=1;i<=row;i++)
for(int j=1;j<=col;j++)
{
cin>>a[i][j];
if(a[i][j]=='.')
n++,spot[count_++]=(i-1)*col+j;
if(a[i][j]=='S')
s=(i-1)*col+j;
}
for(int i=1;i<=row;i++)
for(int j=1;j<=col;j++)
if(a[i][j]=='C')
{
a[i][j]='K';
for(int z=i;z<=row && a[z][j]!='W';z++)
{
if(a[z][j]=='.')
a[z][j]='K';
if(a[z][j]=='S')
{
for(int h=0;h<n;h++)
cout<<"-1"<<endl;
return 0;
}
}
for(int z=i-1;z>=1 && a[z][j]!='W';z--)
{
if(a[z][j]=='.')
a[z][j]='K';
if(a[z][j]=='S')
{
for(int h=0;h<n;h++)
cout<<"-1"<<endl;
return 0;
}
}
for(int z=j+1;z<=col && a[i][z]!='W';z++)
{
if(a[i][z]=='.')
a[i][z]='K';
if(a[i][z]=='S')
{
for(int h=0;h<n;h++)
cout<<"-1"<<endl;
return 0;
}
}
for(int z=j-1;z>=1 && a[i][z]!='W';z--)
{
if(a[i][z]=='.')
a[i][z]='K';
if(a[i][z]=='S')
{
for(int h=0;h<n;h++)
cout<<"-1"<<endl;
return 0;
}
}
}
for(int i=1;i<=row;i++)
for(int j=1;j<=col;j++)
if(a[i][j]=='K')
a[i][j]='W';
edge temp;
for(int i=1;i<=row;i++)
{
for(int j=1;j<=col;j++)
{
if(a[i][j]=='.' || a[i][j]=='S')
{
for(int p=0;p<4;p++)
if(i+fx[p]>=1 && i+fx[p]<=row && j+fy[p]>=1 && j+fy[p]<=col && a[i+fx[p]][j+fy[p]]!='W')
{
if(!visit[(i-1)*col+j][(i+fx[p]-1)*col+j+fy[p]])
{
visit[(i-1)*col+j][(i+fx[p]-1)*col+j+fy[p]]=true;
temp.to=(i+fx[p]-1)*col+j+fy[p];
temp.cost=1;
graph[(i-1)*col+j].push_back(temp);
}
if(!visit[(i+fx[p]-1)*col+j+fy[p]][(i-1)*col+j] && a[i+fx[p]][j+fy[p]]=='.')
{
visit[(i+fx[p]-1)*col+j+fy[p]][(i-1)*col+j]=true;
temp.to=(i-1)*col+j;
temp.cost=1;
graph[(i+fx[p]-1)*col+j+fy[p]].push_back(temp);
}
}
}
else if(a[i][j]!='W' && a[i][j]!='.' && a[i][j]!='S')
{
if(a[i][j]=='L')
{
if(j-1<1 || a[i][j-1]=='W')
{
a[i][j]='W';
continue;
}
if(!visit[(i-1)*col+j][(i-1)*col+j-1])
{
visit[(i-1)*col+j][(i-1)*col+j-1]=true;
temp.to=(i-1)*col+j-1;
temp.cost=0;
graph[(i-1)*col+j].push_back(temp);
}
}
if(a[i][j]=='R')
{
if(j+1>col || a[i][j+1]=='W')
{
a[i][j]='W';
continue;
}
if(!visit[(i-1)*col+j][(i-1)*col+j+1])
{
visit[(i-1)*col+j][(i-1)*col+j+1]=true;
temp.to=(i-1)*col+j+1;
temp.cost=0;
graph[(i-1)*col+j].push_back(temp);
}
}
if(a[i][j]=='D')
{
if(i+1>row || a[i+1][j]=='W')
{
a[i][j]='W';
continue;
}
if(!visit[(i-1)*col+j][(i)*col+j])
{
visit[(i-1)*col+j][(i)*col+j]=true;
temp.to=(i)*col+j;
temp.cost=0;
graph[(i-1)*col+j].push_back(temp);
}
}
if(a[i][j]=='U')
{
if(i-1<1 || a[i-1][j]=='W')
{
a[i][j]='W';
continue;
}
if(!visit[(i-1)*col+j][(i-2)*col+j])
{
visit[(i-1)*col+j][(i-2)*col+j]=true;
temp.to=(i-2)*col+j;
temp.cost=0;
graph[(i-1)*col+j].push_back(temp);
}
}
}
}
}
dijkstra(s);
for(int i=0;i<count_;i++)
{
if(spot[i]==s)
continue;
if(d[spot[i]]==INF)
cout<<"-1"<<endl;
else
cout<<d[spot[i]]<<endl;
}
return 0;
} OKay，现在是正常的DFS：（由我们学校一位神犇写的）
（但其实这个代码是有点问题的，知道错在哪里嘛？）
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
int n,m,stx,sty;
char map[102][102];
vector<int> endx;
vector<int> endy;
int sht[102][102];
int mapp[102][102]={0};
void dfs(int x,int y,int step)
{
if(mapp[x][y]==1)
return;
if(step>=sht[x][y])
return;
else
sht[x][y]=step;
if(map[x][y]=='L')
{
dfs(x,y-1,step);
return;
}
if(map[x][y]=='R')
{
dfs(x,y+1,step);
return;
}
if(map[x][y]=='U')
{
dfs(x-1,y,step);
return;
}
if(map[x][y]=='D')
{
dfs(x+1,y,step);
return;
}
if(mapp[x+1][y]==0)
dfs(x+1,y,step+1);
if(mapp[x-1][y]==0)
dfs(x-1,y,step+1);
if(mapp[x][y+1]==0)
dfs(x,y+1,step+1);
if(mapp[x][y-1]==0)
dfs(x,y-1,step+1);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>map[i][j];
if(map[i][j]=='.')
{
endx.push_back(i);
endy.push_back(j);
}
if(map[i][j]=='S')
{
stx=i;
sty=j;
}
if(map[i][j]=='W')
{
mapp[i][j]=1;
}
sht[i][j]=30000;
}
}
for(int i=0;i<=n;i++)
mapp[i][0]=mapp[i][m+1]=1;
for(int i=0;i<=m;i++)
mapp[0][i]=mapp[n+1][i]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(map[i][j]=='C')
{
for(int x=i;x<=n;x++)
{
if(map[x][j]=='W')
break;
else if(map[x][j]=='.')
mapp[x][j]=1;
}
for(int x=i;x>0;x--)
{
if(map[x][j]=='W')
break;
else if(map[x][j]=='.')
mapp[x][j]=1;
}
for(int y=j;y<=m;y++)
{
if(map[i][y]=='W')
break;
else if(map[i][y]=='.')
mapp[i][y]=1;
}
for(int y=j;y>0;y--)
{
if(map[i][y]=='W')
break;
else if(map[i][y]=='.')
mapp[i][y]=1;
}
}
}
}
dfs(stx,sty,0);
for(int i=0;i<endx.size();i++)
{
if(sht[endx[i]][endy[i]]==30000)
cout<<-1<<endl;
else
cout<<sht[endx[i]][endy[i]]<<endl;
}
return 0;
}接下来是我用BFS又写了一遍：
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N=111;
int n,m;
char a[N][N];
int ans[N][N];
int sx=-1,sy;
const int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
bool checkIn(int x,int y)
{
return 0<=x && x<n && 0<=y && y<m;
}
void input()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%s", a[i]);
for(int j=0;j<m;j++)
{
if (a[i][j] == 'S')
sx = i, sy = j;
ans[i][j]=-1;
}
}
}
struct Point
{
int x,y;
Point(int x,int y):x(x),y(y){}
int getAns()const
{
return ans[x][y];
}
char get()const
{
return a[x][y];
}
bool operator<(const Point &p)const
{
if(getAns()!=p.getAns())
return getAns()>p.getAns();
if(x!=p.x)
return x<p.x;
return y<p.y;
}
};
void bfs(int sx,int sy)
{
priority_queue<Point> Q;
ans[sx][sy]=0;
Q.push(Point(sx,sy));
while(!Q.empty())
{
Point u=Q.top();
Q.pop();
int dmin=0,dmax=3;
if (u.get()=='U')
dmin=dmax=0;
else if(u.get()=='D')
dmin=dmax=1;
else if(u.get()=='L')
dmin=dmax=2;
else if(u.get()=='R')
dmin=dmax=3;
for(int d=dmin;d<=dmax;d++)
{
Point v(u.x+dir[d][0],u.y+dir[d][1]);
if(!checkIn(v.x,v.y))
continue;
if(v.get()=='W')
continue;
if(v.get()=='C')
continue;
if(v.getAns()!=-1)
continue;
ans[v.x][v.y]=u.getAns()+(a[v.x][v.y]=='.'?1:0);
Q.push(v);
}
}
}
void solve()
{
bool flag=true;
for(int i=0;i<n && flag;i++)
for(int j=0;j<m && flag;j++)
{
if (a[i][j] == 'C')
for (int d = 0; d < 4 && flag; d++)
for (int x = i, y = j; flag && checkIn(x, y) && a[x][y] != 'W'; x += dir[d][0], y += dir[d][1])
{
if (a[x][y] == '.')
ans[x][y] = -2;
if (a[x][y] == 'S')
flag = false;
}
}
if(!flag)
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
ans[i][j]=-1;
else
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(a[i][j]=='S')
{
bfs(i, j);
break;
}
}
void output()
{
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(a[i][j]=='.')
printf("%d\n",ans[i][j]<0?-1:ans[i][j]);
}
int main()
{
input();
solve();
output();
return 0;
}
类似资料：