fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define mp make_pair
  3. #define pb push_back
  4. #define vi vector<int>
  5. #define pii pair<int,int>
  6. #define vii vector<pii>
  7. #define rep(i,n) for(int i = 0; i < n; i++)
  8. #define rp(i,a,n) for(int i=a;i<=int(n);i++)
  9. #define IT(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
  10. #define all(x) (x).begin(), (x).end()
  11. #define ll long long
  12. #define sc(x) scanf("%d", &x)
  13. #define oo INT_MAX
  14. #define fill(a,b) memset(a,b,sizeof a)
  15. #define F first
  16. #define S second
  17. #define mod 1000000007
  18. #define N 100005
  19. using namespace std;
  20. int dh[4] = {0, 1, 0, -1};
  21. int dv[4] = {-1, 0, 1, 0};
  22. //code
  23. int a[50][50],s,n,ans,t;
  24. bool ok(int x,int y)
  25. {
  26.     if(x<0||y<0||x>=n||y>=n) return false;
  27.     return true;
  28. }
  29. void dfs(int x,int y,int c,int ss,int mask)
  30. {
  31.     if(!ok(x,y)||ans<c||ss>t) return ; // make sure current cost is not less than the min cost already found
  32.     if(x==0&&y==n-1&&ss>=s) { ans=min(ans,c);return; } 
  33.     int z=a[x][y];
  34.     if(z&&!(mask&(1<<z))) {ss++;mask=mask | (1 << z);} // make sure that z is not taken before
  35.     dfs(x+1,y,c+1,ss,mask);
  36.     dfs(x,y+1,c+1,ss,mask);
  37.     dfs(x-1,y,c+1,ss,mask);
  38.     dfs(x,y-1,c+1,ss,mask);
  39. }
  40. int main()
  41. {
  42.     int x,y,cas=0;
  43.     while(1)
  44.     {
  45.         scanf("%d %d %d",&n,&t,&s);
  46.         if(!n&&!t&&!s) break;
  47.         rep(i,35)rep(j,35) a[i][j]=0;ans=905;
  48.         rep(i,t) { cin >> x >> y ; a[n-1-x][y]=i+1; } // mark each treasure with a number i (1..t)
  49.         dfs(n-1,0,0,0,0);
  50.         printf("Case %d: %d\n",++cas,ans);
  51.     }
  52.  
  53. }
  54.  
Success #stdin #stdout 0s 2692KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/61YnMl
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!