求助站外题(一道简单的迷宫问题)
查看原帖
求助站外题(一道简单的迷宫问题)
856165
邦邦家的雷达站楼主2023/7/12 10:17

题目是下面这个

设有一个n×n的方格迷宫,入口和出口分别在左上角和右上角(如图的示)

迷宫的格子分别放有0和1,0表示可通,1表示不能,迷宫走的规则如下图所示。

即从某点出发,可沿8个方向前进,前进方格中的数为0时表示可以通过,为1时表示不可以通过,如从入口开始,有2条路可以走,即向右走,或向右下角走,当迷宫给出后,找出一条从入口(1,1)到出口(1,8)的有多少条不同的中路径。

输入格式 一个数 n,接着一个 n 行 n 列的矩阵表示迷宫。

输出格式 一个数表示路径数量。

样例 【样例输入】

8

0 0 0 1 1 0 1 0

1 0 1 1 0 1 1 0

0 1 0 0 1 0 0 1

0 0 1 1 0 1 0 1

0 1 0 0 0 1 1 0

0 1 1 1 1 1 0 1

0 0 1 1 1 0 1 1

1 1 0 0 0 0 0 0

【样例输出】

720

但本蒟蒻的代码一直输出0......


代码如下!

#include<bits/stdc++.h>
using namespace std;

int n,ans;
int a[1145][1145],v[1145][1145];
int ax[10]={0,-1,-1,-1,0,1,1,1};
int ay[10]={1,1,0,-1,-1,-1,0,1};

void dfs(int x,int y) {
	if(x==0&&y==n) {
		ans++;
		return ;
	}
	for(int i=0;i<8;i++) {
		int nx=x+ax[i],ny=y+ay[i];
		if(a[nx][ny]==0&&nx>=0&&nx<n&&ny>=0&&ny<n&&v[nx][ny]==0) {
			v[nx][ny]=1;
			dfs(nx,ny);
			v[nx][ny]=0;
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n;
	n--;
	for(int i=0;i<=n;i++) {
		for(int j=0;j<=n;j++) cin>>a[i][j];
	}
	dfs(0,0);
	cout<<ans;
	return 0;
}

求修改!

2023/7/12 10:17
加载中...