求助,不明原因WA了
查看原帖
求助,不明原因WA了
564225
dontwannacry楼主2022/8/13 11:21
#include<bits/stdc++.h>
using namespace std;
int N,M,tx[2],ty[2],w[510][510] = {0},ans;
struct zb{
	int x,y;
}link;
queue<zb>q;
string A;
void ql(){
	for(int i = 1;i <= N;++i){
		for(int j = 1;j <= M;++j){
			if(w[i][j]!=-1){
				w[i][j] = 0;
			}
		}
	}
	while(!q.empty()){
		q.pop();
	}
}
int main(){
	//freopen("a.txt","r",stdin);
	cin >> N >> M;
	for(int i = 1;i <= N;++i){
		cin >> A;
		for(int j = 0;j < M;++j){
			if(A[j] == '#'){
				w[i][j+1]=-1;
			}else if(A[j] == 'C'){
				tx[0] = i;ty[0] = j+1;
			}else if(A[j] == 'S'){
				link.x = i;link.y = j+1;
			}else if(A[j] == 'G'){
				tx[1] = i;ty[1] = j+1;
			}
		}
	}
	q.push(link);
	bool flag = 1;
	w[link.x][link.y] = 1;
	while(!q.empty()){
		link = q.front();
		if(link.x==tx[0]&&link.y==ty[0]){
			ans+=w[tx[0]][ty[0]]-1;
			flag = 0;
			break;
		}
		zb link1 = link,link2 = link,link3=link,link4=link;
		link1.x++;link2.x--;link3.y++;link4.y--;
		if(w[link1.x][link1.y] == 0){
			w[link1.x][link1.y] = w[link.x][link.y]+1;
			q.push(link1);
		}if(w[link2.x][link2.y] == 0){
			w[link2.x][link2.y] = w[link.x][link.y]+1;
			q.push(link2);
		}if(w[link3.x][link3.y] == 0){
			w[link3.x][link3.y] = w[link.x][link.y]+1;
			q.push(link3);
		}if(w[link4.x][link4.y] == 0){
			w[link4.x][link4.y] = w[link.x][link.y]+1;
			q.push(link4);
		}
		q.pop();
	}
	if(flag){
		cout << "-1";
		return 0;
	}
	ql();
	flag = 1;
	link.x = tx[0];link.y = ty[0];
	q.push(link);
	w[link.x][link.y] = 1;
	while(!q.empty()){
		link = q.front();
		if(link.x==tx[1]&&link.y==ty[1]){
			ans+=w[tx[1]][ty[1]]-1;
			flag = 0;
			break;
		}
		zb link1 = link,link2 = link,link3=link,link4=link;
		link1.x++;link2.x--;link3.y++;link4.y--;
		if(w[link1.x][link1.y] == 0){
			w[link1.x][link1.y] = w[link.x][link.y]+1;
			q.push(link1);
		}if(w[link2.x][link2.y] == 0){
			w[link2.x][link2.y] = w[link.x][link.y]+1;
			q.push(link2);
		}if(w[link3.x][link3.y] == 0){
			w[link3.x][link3.y] = w[link.x][link.y]+1;
			q.push(link3);
		}if(w[link4.x][link4.y] == 0){
			w[link4.x][link4.y] = w[link.x][link.y]+1;
			q.push(link4);
		}
		q.pop();
	}
	if(flag){
		cout << "-1";
		return 0;
	}
	cout << ans;
	return 0;
}
2022/8/13 11:21
加载中...