题解 P2802 【回家】

lrj124 · 2016-07-28 11:00:45 · 题解

我居然是第一个发题解的

DFS+剪枝

剪枝：若现在的路程以大于原来的最小值，结束

代码：

#include <bits/stdc++.h>
using std :: min;
int map[10][10],n,m,Min = 9999999;
bool vis[10][10];
void dfs(int x,int y,int tot,int now) {
  if (!now || !map[x][y] || !vis[x][y]) return;   //没有生命，或者(x,y)是障碍物，或者已走过此路
  if (x < 1 || x > n || y < 1 || y > m) return;   //出界
  if (tot > Min) return;   //剪枝
  if (map[x][y] == 3) {   //到达终点
    Min = min(tot,Min); 
    return;
  }
  int now1 = now-1;
  if (map[x][y] == 4) now1 = 5; //加生命
  vis[x][y] = false;   //标记已走过
  dfs(x-1,y,tot+1,now1);   //上
  dfs(x+1,y,tot+1,now1);  //下
  dfs(x,y-1,tot+1,now1);   //左
  dfs(x,y+1,tot+1,now1);  //右
  vis[x][y] = true;   //还原
}
int main() {
  int x,y;
  scanf("%d%d",&n,&m);
  memset(vis,true,sizeof(vis));
  for (int i = 1;i <= n;i++)
    for (int j = 1;j <= m;j++) {
          scanf("%d",&map[i][j]);
      if (map[i][j] == 2) x = i,y = j;   //记下起点
      }
  dfs(x,y,0,6);
  if (Min == 9999999) printf("%d",-1);   //无解处理
  else printf("%d",Min);
}