40分求助
  • 板块P1605 迷宫
  • 楼主linrun0504
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/31 18:39
  • 上次更新2024/7/31 19:56:52
查看原帖
40分求助
1349739
linrun0504楼主2024/7/31 18:39
#include<bits/stdc++.h>
using namespace std;
#define N 100005
int head[N],a[105][105];int n,m,z,cnt,q1,q2,z1,z2,sum=0;
bool flag,vis[N];
int getid(int x,int y){
	return (x-1)*m+y;
}
struct node{
	int v,nxt;
};
node e[N];
bool pd(int x,int y){
	return (x>=1)&&(x<=n)&&(y>=1)&&(y<=m)&&a[x][y];
}
void add(int u,int v){
	e[++cnt].v=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
} 
void dfs(int u){
	if(u==getid(n,m)){
		sum++;
		flag=true;
		return;
	}
	vis[u]=true;
	for(int i=head[u];i;i=e[i].nxt){
		if(!vis[e[i].v]) {
			dfs(e[i].v);	
		}
	}
}
int main(){
	cin>>n>>m>>z>>q1>>q2>>z1>>z2;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			a[i][j]=1;
		}
	}
	for(int i=1;i<=z;i++){
		int za1,za2;
		cin>>za1>>za2;
		a[za1][za2]=0;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
				if(pd(i-1,j)) add(getid(i,j),getid(i-1,j));
				if(pd(i+1,j)) add(getid(i,j),getid(i+1,j));
				if(pd(i,j-1)) add(getid(i,j),getid(i,j-1));
				if(pd(i,j+1)) add(getid(i,j),getid(i,j+1));
		}
	}
	dfs(getid(1,1));
	cout<<sum;
    return 0;  
}
2024/7/31 18:39
加载中...