2018年2/3月月赛 Day1 疯狂的机器人题解

题目描述

MH：“前几个月给一个机器人写了段代码，发现它只能往两个方向走，不能回退，而且还是随机的，真是无语…”

CL：“我看你也够随机的，最后那家伙竟然疯了一样，在上下左右四个方向乱走了，可真是吓死我了”

MH：“是啊是啊。我记下了它当时的所在的地图，希望能找到它最远可能从哪里来的”

还是机智的你，知道这个机器人最远可能从哪里来的吗？

输入输出格式

输入格式

第一行两个正整数n,m，表示机器人所在地图的规模。

第2行到第n+1行，每行m个数字，分别是0,1,-1三种之一。

其中，0表示可以行走的路，1表示墙壁，-1表示机器人所在的坐标。

输出格式

一行，包含一个数字。若能有最远可到达的地方，输出该距离，否则输出0。

输入输出样例

输入样例#1：

输出样例#1：

输入样例#2：

输出样例#2：

说明

对于100%的数据，1<=n,m<=50。

定性为搜索题，搜索所有点中到起点走最短路仍最远的地方，也就是求起点到所有点的最短距离的最大值。

此处采用dfs。使用bfs的话需要有明确的终点，而本题没有固定终点，因此不适合bfs。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,final=0,d[60][60],ans[60][60]={0},stx,sty;
void dfs(int x,int y)
{
  for(int i=x-1;i<=x+1;i++)
  {
      if(i<0||i>=n) continue;
      for(int j=y-1;j<=y+1;j++)
      {
          if(j<0||j>=m) continue;
          if(i==stx&&j==sty) continue;
          if(i==x&&y==j) continue;
          if(i!=x&&y!=j) continue;
          if(d[i][j]) continue;
          int &t=ans[i][j];
          if(!t||(t&&t>ans[x][y]+1))
          {
              t=ans[x][y]+1;
              dfs(i,j);
          }
      }
  }
}
int main()
{
  cin>>n>>m;
  for(int i=0;i<n;i++)
  {
      for(int j=0;j<m;j++)
      {
          cin>>d[i][j];
          if(d[i][j]==-1)
          {
              stx=i;
              sty=j;
          }
      }
  }
  dfs(stx,sty);
  for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(final<ans[i][j]) final=ans[i][j];
  cout<<final;
  return 0;
}