Register
|
Login
Home
News
Competitions
Practice
How to
Rankings
Calendar
Arena
CodeFu 2010
CodeFu'10 Highlights
Jazoon'10 Highlights
Schedule
Rules
Prizes
Results
Competitions
»
Main CodeFu Competitons
»
CodeFu 2010
»
Results
CodeFu 2010 Results
Final Round Results
vasja's solution for 400: GivesYouWings, written in C++, submitted on 09.05.2010 13:55:05
#include <string> #include <vector> #include<queue> #include<iostream> using namespace std; class GivesYouWings { public: int calc(int br) { int res=256; while(br>0) { res/=2; br--; } return res; } int solve(vector<string> maze) { int n=maze.size(); int m=maze[0].size(); int i,j,k; int si,sj; int ei,ej; int di[]={-1,+1,0,0}; int dj[]={0,0,-1,+1}; int red_bul[31][31]; int cnt; int vis[n+1][m+1][1<<9]; memset(red_bul,-1,sizeof(red_bul)); memset(vis,62,sizeof(vis)); queue<int> qi,qj,qmask; int I,J,mask; cnt=0; for(i=0;i<n;i++) for(j=0;j<m;j++) { if(maze[i][j]=='S') {si=i; sj=j;} if(maze[i][j]=='T') {ei=i; ej=j;} if(maze[i][j]=='*') {red_bul[i][j]=cnt; cnt++;} } mask=0; qi.push(si); qj.push(sj); qmask.push(mask); vis[si][sj][mask]=0; int new_mask; while(!qi.empty()) { I=qi.front(); J=qj.front(); mask=qmask.front(); //cout<<I<<" "<<J<<" "<<mask<<endl; qi.pop(); qj.pop(); qmask.pop(); for(k=0;k<4;k++) { int ii=I+di[k]; int jj=J+dj[k]; if(ii>=0 && ii<n && jj>=0 && jj<m && maze[ii][jj]!='#') { int time=calc( __builtin_popcount(mask) ); if(maze[ii][jj]=='*' && (mask & (1<<red_bul[ii][jj]))==0 ) //ako treba da zeme red_bull { new_mask=(mask|(1<<red_bul[ii][jj])); if(vis[I][J][mask] + time < vis[ii][jj][new_mask]) { vis[ii][jj][new_mask]=vis[I][J][mask] + time; qi.push(ii); qj.push(jj); qmask.push(new_mask); } } else //ako nema red_bull { if(vis[I][J][mask]+time<vis[ii][jj][mask]) { vis[ii][jj][mask]=vis[I][J][mask]+time; qi.push(ii); qj.push(jj); qmask.push(mask); } } } } } /* for(i=0;i<n;i++) { for(j=0;j<m;j++) { if(vis[i][j][0]>10000) cout<<"-1 "; else cout<<vis[i][j][0]<<" "; } cout<<endl; } */ int res=1000000000; for(i=0;i<(1<<9);i++) if(vis[ei][ej][i]<res) res=vis[ei][ej][i]; if(res==1000000000) return -1; return res; } }