GitBook

这里写图片描述 这里写图片描述

虽然学长把这题取名为BFS…… 不过一时脑抽没分清BFS是深搜还是广搜 所以用的DFS做的

不过对于这种水题其实都一样啦 没什么坑点 用一个二维数组保存每个点到终点的距离 然后递归搜索 遇见x就+2 遇见.就+1

#include<stdio.h>
int inf=9999999;
char map[220][220];
int dis[220][220];
int n,m;
int mn,mm;
int en,em;
void bfs(int tn,int tm) {
	if(tm+1<m&&((map[tn][tm+1]=='.'&&dis[tn][tm+1]>=dis[tn][tm]+1)||(map[tn][tm+1]=='x'&&dis[tn][tm+1]>=dis[tn][tm]+2))) {
		dis[tn][tm+1]=dis[tn][tm]+1;
		if(map[tn][tm+1]=='x')
			dis[tn][tm+1]++;
		bfs(tn,tm+1);
	}
	if(tm-1>=0&&((map[tn][tm-1]=='.'&&dis[tn][tm-1]>=dis[tn][tm]+1)||(map[tn][tm-1]=='x'&&dis[tn][tm-1]>=dis[tn][tm]+2))) {
		dis[tn][tm-1]=dis[tn][tm]+1;
		if(map[tn][tm-1]=='x')
			dis[tn][tm-1]++;
		bfs(tn,tm-1);
	}
	if(tn-1>=0&&((map[tn-1][tm]=='.'&&dis[tn-1][tm]>=dis[tn][tm]+1)||(map[tn-1][tm]=='x'&&dis[tn-1][tm]>=dis[tn][tm]+2))) {
		dis[tn-1][tm]=dis[tn][tm]+1;
		if(map[tn-1][tm]=='x')
			dis[tn-1][tm]++;
		bfs(tn-1,tm);
	}
	if(tn+1<n&&((map[tn+1][tm]=='.'&&dis[tn+1][tm]>=dis[tn][tm]+1)||(map[tn+1][tm]=='x'&&dis[tn+1][tm]>=dis[tn][tm]+2))) {
		dis[tn+1][tm]=dis[tn][tm]+1;
		if(map[tn+1][tm]=='x')
			dis[tn+1][tm]++;
		bfs(tn+1,tm);
	}
}
int main() {
	while(scanf("%d %d",&n,&m)!=EOF) {
		getchar();
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				dis[i][j]=inf;
				scanf("%c",&map[i][j]);
				if(map[i][j]=='r') {
					mn=i;
					mm=j;
					dis[i][j]=0;
				} else if(map[i][j]=='a') {
					en=i;
					em=j;
					map[i][j]='.';
				}
			}
			getchar();
		}
		bfs(mn,mm);
		if(dis[en][em]==inf)
			printf("Poor ANGEL has to stay in the prison all his life.\n");
		else
			printf("%d\n",dis[en][em]);
	}
	return 0;
}

题目记录:【杭电】[1242]Rescue