蒟蒻求助:为什么有些点会WA?
查看原帖
蒟蒻求助:为什么有些点会WA?
222104
_yjh楼主2020/5/14 12:19
#include<iostream>
using namespace std;
struct Pos {
	int x,y;
};
int n,m,sx,sy,sum=0,ans=2147483647;
char mp[305][305];
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
int vis[305][305];
Pos ZM1[27],ZM2[27];
void dfs(int x,int y) {
	if(sum>=ans) {
		return ;
	}
	for(int i=0;i<=3;i++) {
	    int tx=x+dx[i];
		int ty=y+dy[i];
		if(tx<=0||tx>n||ty<=0||ty>m) continue;
		if(mp[tx][ty]=='#'||vis[tx][ty]==true) continue;
		if(mp[tx][ty]=='=') {
			sum++;
	    	ans=min(sum,ans);
	    	sum--;
    		return ;
    	}
		if(mp[tx][ty]=='.') {
			sum++;
			vis[tx][ty]=true;
			dfs(tx,ty);
			sum--;
			vis[tx][ty]=false;
		} 
		else {
			int xx=tx,yy=ty;
			sum++;
			vis[xx][yy]=true;
			int num=int(mp[tx][ty])-64;
			if(ZM1[num].x==tx&&ZM1[num].y==ty) {
			    tx=ZM2[num].x;
			    ty=ZM2[num].y;
			} 
			else {
				tx=ZM1[num].x;
			    ty=ZM1[num].y;
			}
			vis[tx][ty]=true;
		    dfs(tx,ty);
			vis[tx][ty]=false;
			vis[xx][yy]=false;
			sum--;
			tx=xx,ty=yy;
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			cin>>mp[i][j];
			if(mp[i][j]=='@') {
				sx=i,sy=j;
			}
			if(mp[i][j]>='A'&&mp[i][j]<='Z') {
				if(ZM1[mp[i][j]-64].x*ZM1[mp[i][j]-64].y==0) {
					ZM1[mp[i][j]-64].x=i,ZM1[mp[i][j]-64].y=j;
				}
				else ZM2[mp[i][j]-64].x=i,ZM2[mp[i][j]-64].y=j;
			}
		}
	}
	for(int i=1;i<=26;i++) {
		if(ZM1[i].x!=0&&ZM2[i].x==0) {
			mp[ZM1[i].x][ZM1[i].y]='.';
		}
	}
	dfs(sx,sy);
	cout<<ans<<'\n';
	return 0;
} 

2020/5/14 12:19
加载中...