首页 > 代码库 > bzoj 1493 暴力
bzoj 1493 暴力
我们可以枚举每个点,然后求出这个点到其余点最小消耗的代价,求出比t小的且距离最大的更新答案。
/************************************************************** Problem: 1295 User: BLADEVIL Language: C++ Result: Accepted Time:4572 ms Memory:3944 kb ****************************************************************/ //By BLADEVIL #include <cmath> #include <cstdio> #include <cstring> #define maxn 400 using namespace std; int n,m,T; char s[maxn]; int map[maxn][maxn],quex[maxn*maxn],quey[maxn*maxn],dis[maxn][maxn],flag[maxn][maxn]; int go[5][2]; double ans; double max(double a,double b) { if (a>b) return a; else return b; } int main() { go[1][0]=go[4][1]=-1; go[2][1]=go[3][0]=1; scanf("%d%d%d",&n,&m,&T); for (int i=1;i<=n;i++) { scanf("%s",s+1); for (int j=1;j<=m;j++) map[i][j]=s[j]!=‘0‘?1:0; } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { memset(dis,127,sizeof dis); memset(flag,0,sizeof flag); quex[1]=i; quey[1]=j; dis[i][j]=(map[i][j]==1); int h(0),t(1); while (h<t) { h=(h%2000)+1; int curx(quex[h]),cury(quey[h]); flag[curx][cury]=0; for (int k=1;k<=4;k++) { int nx(curx+go[k][0]),ny(cury+go[k][1]); if ((nx<1)||(nx>n)||(ny<1)||(ny>m)) continue; if (dis[curx][cury]+(map[nx][ny]==1)<dis[nx][ny]) { dis[nx][ny]=dis[curx][cury]+(map[nx][ny]==1); if (!flag[nx][ny]) { t=(t%2000)+1; quex[t]=nx; quey[t]=ny; flag[nx][ny]=1; } } } } for (int ii=1;ii<=n;ii++) for (int jj=1;jj<=m;jj++) if (dis[ii][jj]<=T) ans=max(ans,(ii-i)*(ii-i)+(jj-j)*(jj-j)); } ans=sqrt(ans); printf("%.6f\n",ans); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。