搜索 专题

题目链接：洛谷 P1605 迷宫

题目描述

输入输出格式

时空限制

  • 时间：1000ms
  • 空间：128MB

思路

因为数据比较弱，所以可以先初始化迷宫都为没有障碍，即都可以走路，然后随着输入实时更新迷宫障碍。同时，把每次可以移动的 x 、y 用数据记录，这样每次只要加上相应的 walkx 和 walky 就行。最后，用 深度优先搜索 ，就能得出答案了。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int barrier[10][10];
int walkx[5] = {0,0,0,1,-1};  //x方向可以走的选择
int walky[5] = {0,-1,1,0,0};  //y方向可以走的选择
int n,m,t,sx,sy,fx,fy;  //n行，m列，t障碍数，sx,sy起点坐标，fx,fy终点坐标 
int result = 0;
int flag[10][10];

void dfs(int x, int y){
	if(x == fx && y == fy){
		result++;
		return;  //返回 
	}
	else{
		for(int i = 1; i <= 4; ++i){  //上下左右四个方向可以走 
			if(flag[x+walkx[i]][y+walky[i]] == 0
			 && barrier[x+walkx[i]][y+walky[i]] == 1){  //是否已走过 && 是否有障碍 
				flag[x][y] = 1;  //原先的标记为已走过 
				dfs(x+walkx[i],y+walky[i]);
				flag[x][y] = 0;  //回溯 
			}
		}
	}
}

int main(){
	scanf("%d%d%d",&n,&m,&t);
	scanf("%d%d%d%d",&sx,&sy,&fx,&fy);
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			barrier[i][j] = 1;  //初始化为地图都不为障碍，即都可以走 
		}
	}
	int barrierx,barriery;
	for(int i = 1; i<= t; ++i){
		scanf("%d%d",&barrierx,&barriery);
		barrier[barrierx][barriery] = 0;  //更新障碍处 
	}
	dfs(sx,sy);  //从起点开始深搜 
	printf("%d\n",result);
	return 0;
}