求助,70分
查看原帖
求助,70分
601245
I_am_zhima楼主2023/10/8 13:59
#include<bits/stdc++.h>
using namespace std;
#define re register
#define int long long
#define pii pair<int,int>
const int N=1005,inf=1<<27;

int n,m;

int sx,sy,ex,ey;
char a[N][N];
int vis[N][N];

queue<pii> q;

inline bool check(int x,int y){
	if(x<1||x>n||y<1||y>m||vis[x][y]||a[x][y]=='*')
		return 0;
	return 1;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	cin>>m>>n;
	for(re int i=1;i<=n;i++)
		for(re int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]=='C'){
				if(!sx)
					sx=i,sy=j;
				else
					ex=i,ey=j;
			}
		}
	
	q.push(make_pair(sx,sy));vis[sx][sy]=1;
	
	int tmp=1;
	while(check(tmp+sx,sy)) vis[tmp+sx][sy]=1,q.push(make_pair(tmp+sx,sy)),tmp++;
	tmp=1;
	while(check(sx-tmp,sy)) vis[sx-tmp][sy]=1,q.push(make_pair(sx-tmp,sy)),tmp++;
	tmp=1;
	while(check(sx,sy+tmp)) vis[sx][sy+tmp]=1,q.push(make_pair(sx,tmp+sy)),tmp++;
	tmp=1;
	while(check(sx,sy-tmp)) vis[sx][sy-tmp]=1,q.push(make_pair(sx,sy-tmp)),tmp++;
	
//	cout<<sx<<" "<<sy<<"\n";
//	for(re int i=1;i<=n;i++){
//		for(re int j=1;j<=m;j++){
//			cout<<vis[i][j]<<" ";
//		}
//		cout<<"\n";
//	}cout<<"\n";
	
	while(!q.empty()){
		int x=q.front().first,y=q.front().second;q.pop();
		
		if(x==ex&&y==ey){
			cout<<vis[x][y]-1<<"\n";
			break;
		}
		
		tmp=1;
		while(check(tmp+x,y)) vis[tmp+x][y]=vis[x][y]+1,q.push(make_pair(tmp+x,y)),tmp++;
		tmp=1;
		while(check(x-tmp,y)) vis[x-tmp][y]=vis[x][y]+1,q.push(make_pair(x-tmp,y)),tmp++;
		tmp=1;
		while(check(x,y+tmp)) vis[x][y+tmp]=vis[x][y]+1,q.push(make_pair(x,tmp+y)),tmp++;
		tmp=1;
		while(check(x,y-tmp)) vis[x][y-tmp]=vis[x][y]+1,q.push(make_pair(x,y-tmp)),tmp++;
		
//		cout<<x<<" "<<y<<"\n"; 
//		for(re int i=1;i<=n;i++){
//			for(re int j=1;j<=m;j++)
//				cout<<vis[i][j]<<" ";
//			cout<<"\n";
//		}cout<<"\n";
	}
	
	return 0;
}
2023/10/8 13:59
加载中...