2019-06-13 19:45:27 C++

C++

Copy Copied! Full
#include <bits/stdc++.h> using namespace std; char s[1005][1005]; bool v[11]; int g[12][12]; int H,W,N; int ans=1e9+7; int sum; pair<int,int> p[12]; vector<int> root; int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; int bfs(int start,int goal){ if(g[start][goal]!=-1)return g[start][goal]; int sx = p[start].first; int sy = p[start].second; int gx = p[goal].first; int gy = p[goal].second; vector<vector<int>> visited(1005,vector<int>(1005,0)); queue<pair<int,int>>q; visited[sx][sy]=1; q.push({sx,sy}); while(!q.empty()){ pair<int,int> cur = q.front();q.pop(); for(int i=0;i<4;i++){ int nx = cur.first + dx[i]; int ny = cur.second+ dy[i]; if(nx<0||ny<0||nx>=H||ny>=W)continue; if(visited[nx][ny]==0&&s[nx][ny]!='X'){ visited[nx][ny]=visited[cur.first][cur.second]+1; q.push({nx,ny}); if(nx==gx&&ny==gy)break; } } } return g[start][goal]= g[goal][start] = visited[gx][gy]-1; } void dfs(int d,int p,int h,int dis){ if(d==N&&h==1+sum){ ans = min(ans,dis); return; } for(int i=1;i<=N;i++){ if(h>=i&&v[i]==0){ v[i]=1; dfs(d+1,i,h+i,dis+bfs(p,i)); v[i]=0; } } } int main(void){ cin >> H >> W >> N; for(int i=0;i<H;i++)cin >> s[i]; for(int i=0;i<H;i++)for(int j=0;j<W;j++){ for(int x=1;x<=N;x++){ string temp; temp = to_string(x); if(s[i][j]==temp[0]){ p[x].first = i; p[x].second= j; } } if(s[i][j]=='S'){ p[0].first= i; p[0].second=j; } } for(int i=1;i<=N;i++)sum+=i; for(int i=0;i<12;i++)for(int j=0;j<12;j++)g[i][j]=-1; v[0]=1; dfs(0,0,1,0); for(int i=0;i<=N;i++){ for(int j=0;j<=N;j++){ printf("g[%d][%d]=%d\n",i,j,g[i][j]); } } //cout << ans << endl; }
RECOMMEND