Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

爽!C++TLE,G++AC 740ms (bfs+next_permutation()) 附代码

Posted by 20051106 at 2019-06-26 22:27:16 on Problem 2688
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#pragma GCC diagnostic error "-std=c++11"
#define ll long long
#define mp make_pair
using namespace std;
vector<pair<int,int> >v;
char c[22][22];
int bx,by,n,m;
int dist[11][11];
int td[22][22];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
inline int bfs(pair<int,int> a,pair<int,int> b){
	queue<pair<pair<int,int>,int> >q;
	pair<pair<int,int>,int> p;
	memset(td,63,sizeof(td));
	td[a.first][a.second]=0;
	q.push(mp(a,0));
	while(!q.empty()){
		p=q.front();
		q.pop();
		if(p.first==b) return p.second;
		int x=p.first.first,y=p.first.second;
		for(int i=0;i<4;++i){
			int tx=x+dx[i],ty=y+dy[i];
			if(tx<0 or tx==n or ty<0 or ty==m) continue;
			if(td[tx][ty]<=p.second+1 or c[tx][ty]=='x') continue;
			td[tx][ty]=p.second+1;
			q.push(mp(mp(tx,ty),td[tx][ty]));
		}
	}
	return 2147483647;
}
int nxt[12];
inline void solve(){
	v.clear();
	for(int i=0;i<n;++i) for(int j=0;j<m;++j){
		cin>>c[i][j];
		if(c[i][j]=='o') bx=i,by=j;
		else if(c[i][j]=='*') v.push_back(mp(i,j));
	}
	v.insert(v.begin(),mp(bx,by));
	for(int i=0;i<v.size();++i) for(int j=i+1;j<v.size();++j){
		dist[i][j]=dist[j][i]=bfs(v[i],v[j]);
		if(dist[i][j]==2147483647){
			cout<<-1<<endl;
			return;
		}
	}
//	for(int i=0;i<v.size();++i){
//		for(int j=i+1;j<v.size();++j) cout<<i<<' '<<j<<" :  "<<dist[i][j]<<endl;
//	}
//	cout<<endl;
	for(int i=1;i<v.size();++i) nxt[i]=i;
	int mn=2147483647;
	do{
		int cnt=0;
		for(int i=1;i<v.size();++i) cnt+=dist[nxt[i-1]][nxt[i]];
		mn=min(mn,cnt);
//		for(int i=0;i<v.size();++i) cout<<nxt[i]<<' ';
//		cout<<endl<<cnt<<endl;
	}while(next_permutation(nxt+1,nxt+v.size()));
	cout<<mn<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);
	int i,j;
	while(cin>>m>>n){
		if(n and m) solve();
		else break;
	}
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator