c++深搜69分 求助 6、9、11TLE 8、14WA
查看原帖
c++深搜69分 求助 6、9、11TLE 8、14WA
993122
xiaorunrun520楼主2023/6/7 23:55
#include<bits/stdc++.h>
using namespace std;
int n,m,dis[301][301],sx,sy,xx[4] = {0,-1,1,0},yy[4] ={1,0,0,-1};
bool vis[301][301];
char a[301][301]; 
queue<int> q; 
void chuan(int x,int y,char b,int dx,int dy){
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			if(a[i][j] == b && (i!=dx || j!=dy)){
				q.push(i);
				q.push(j);
				dis[i][j] = dis[x][y] + 1;
				return;
			}
		}
	}
}
	
int bfs(int x,int y) {
	while(!q.empty()){
		x = q.front();
		q.pop();
		y = q.front();
		q.pop();
		if(a[x][y] == '=') return dis[x][y];
		for(int i =0;i<=3;i++){
			int dx = x + xx[i];
			int dy = y + yy[i];
			if(a[dx][dy] != '#' && vis[dx][dy] == false){
				if(64 <= a[dx][dy] && a[dx][dy] <= 91){
					char b = a[dx][dy]; 
					chuan(x,y,b,dx,dy);
				}
				else{
					if(a[x][y] < 64 || a[x][y] > 91){
						vis[dx][dy] = true;
					} 
					q.push(dx);
					q.push(dy);
					dis[dx][dy] = dis[x][y] + 1;
				}
			}	
		}	
	}
	return -1;
}
int main(){
	cin>>n>>m;
	bool f = false;
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j] == '@' && !f) {
				sx = i;
				sy = j;
				f = true;
			}
			
		}
	}
	vis[sx][sy] == true;
	q.push(sx);
	q.push(sy);
	cout<<bfs(sx,sy);
}
2023/6/7 23:55
加载中...