求救!调了好几个小时了qwq
查看原帖
求救!调了好几个小时了qwq
1497053
Featherwit022楼主2024/12/30 11:00

Wa#1和#7

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int map[305][305],ans[305][305];
int n,m;
int dx[10]={0,0,1,-1};
int dy[10]={1,-1,0,0};
struct ele{
	int x;
	int y;
	int k;
}e;
queue<ele> q;
void printArr(int arr[305][305]){
	printf("--------------------------\n");
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			printf("%-4d",arr[i][j]);
		}
		printf("\n");
	}
	printf("--------------------------\n");
}
bool check(int x,int y,int k){
	int w=2-(k>0?k-1:0)/m;
	if(e.x-w>0&&e.x+w<=n&&e.y-w>0&&e.y+w<=n&&ans[x][y]==-1){
		for(int i=x-w;i<=x+w;++i){
			for(int j=y-w;j<=y+w;++j){
				if(map[i][j]==0)return 0;
			}
		}
		return 1;
	}
	return 0;
}
void bfs(int x,int y,int k){
	int w;
	e.k=k;
	e.x=x;
	e.y=y;
	q.push(e);
	while(!q.empty()){
		e=q.front();
		q.pop();
		x=e.x;
		y=e.y;
		k=e.k;
		w=2-(k>0?k-1:0)/m;
		if(w){
			e.k=k+1;
			q.push(e);
		}
		if(check(x,y,k)){
			ans[x][y]=k;
			if(x==n-2&&y==n-2)return;
			for(int i=0;i<4;++i){
				e.x=x+dx[i];
				e.y=y+dy[i];
				e.k=k+1;
				q.push(e);
			}
		}
	}
}
int main(){
	cin>>n>>m;
	char c;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			do{
				c=getchar();
			}while(c=='\r'||c=='\n');
			if(c=='+')map[i][j]=1;
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			ans[i][j]=-1;
		}
	}
	bfs(3,3,0);
	cout<<ans[n-2][n-2];
	return 0;
}
2024/12/30 11:00
加载中...