UVA:532 - Dungeon Master
Problem :
https://uva.onlinejudge.org/external/5/532.html//PrOgAmErS@2015 //GRAPHS #include<set> #include<map> #include<cmath> #include<vector> #include<queue> #include<bitset> #include<cstdio> #include<cstring> #include<utility> #include<iostream> #include<algorithm> //#include<sAi> // lAzY ProGrAmEr :) using namespace std; #define MX 10000007 #define LL long long #define ri(x) scanf("%d",&x) #define rl(x) scanf("%lld",&x) #define FOR(i,a,n) for(int i=a;i<n;i++) #define FORE(i,a,n) for(int i=a;i<=n;i++) template<class T1> inline T1 maxi(T1 a,T1 b){return a>b?a:b;} template<class T2> inline T2 mini(T2 a,T2 b){return a<b?a:b;} int dx[]={1,-1,0,0,0,0}; int dy[]={0,0,1,-1,0,0}; int dz[]={0,0,0,0,1,-1}; struct node { int x,y,z; }; int main() { int l,r,c; ri(l),ri(r),ri(c); while(l|r|c) { vector< vector<string> >v1; vector<string>v2; v1.clear(); int ans=0; FOR(i,0,l) { v2.clear(); FOR(j,0,r) { string s; cin>>s; v2.push_back(s); } v1.push_back(v2); } int st_i,st_j,st_k,vis[l+1][r+1][c+1]; node N; memset(vis,0,sizeof vis); FOR(i,0,l) { FOR(j,0,r) { FOR(k,0,c) if(v1[i][j][k]=='S') { N.x=i,N.y=j,N.z=k;break; } } } pair<node,int>P,top; queue< pair<node,int> >Q; Q.push(make_pair(N,0)); vis[N.x][N.y][N.z]=1; while(!Q.empty()) { node K; top=Q.front(); st_i=Q.front().first.x; st_j=Q.front().first.y; st_k=Q.front().first.z; int dist=Q.front().second; Q.pop(); if(v1[st_i][st_j][st_k]=='E') { ans=dist;break; } FOR(i,0,6) { int x1=st_i+dx[i]; int y1=st_j+dy[i]; int z1=st_k+dz[i]; if((x1>=0 and y1>=0 and z1>=0) and (x1<l and y1<r and z1<c) and !vis[x1][y1][z1] and (v1[x1][y1][z1]=='.' or v1[x1][y1][z1]=='E')) { vis[x1][y1][z1]=1; K.x=x1,K.y=y1,K.z=z1; Q.push(make_pair(K,dist+1)); } } } if(ans==0) cout<<"Trapped!\n"; else cout<<"Escaped in "<<ans<<" minute(s)."<<endl; ri(l),ri(r),ri(c); } }
BFS
,
Graph Theory
,
UVA
LeetCode:Happy Numbers
Problem :
https://leetcode.com/problems/happy-number/#include<bits/stdc++.h> using namespace std; class Solution { public: bool isHappy(int n) { map<int,int>a; while(a[n]!=1) { a[n]=1; int sum=0,res=0; while(n) { res=n%10; sum+=(res*res); n/=10; } if(sum==1) return true; else { n=sum; } } return false; } }; int main() { Solution s; cout<<s.isHappy(19)<<endl; cout<<s.isHappy(301)<<endl; }
SPOJ:ABCDEF
Problem :
http://www.spoj.com/problems/ABCDEF/
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define ll long long #define rl(x) scanf("%lld",&x) ll a1[105]; ll arr1[2000000]; int main() { ll n,temp1=0,v,ans=0; rl(n); for(int i=0;i<n;i++) rl(a1[i]); for(int a=0;a<n;a++) if(a1[a]) for(int b=0;b<n;b++) for(int c=0;c<n;c++) arr1[temp1++]=(a1[a]*(a1[b]+a1[c])); sort(arr1,arr1+temp1); for(int d=0;d<n;d++) for(int e=0;e<n;e++) for(int f=0;f<n;f++) { v=a1[d]*a1[e]+a1[f]; ans+=(upper_bound(arr1,arr1+temp1,v))-(lower_bound(arr1,arr1+temp1,v)); } cout<<ans<<endl; }