Lightoj 1066 - Gathering Food

http://lightoj.com/volume_showproblem.php?problem=1066

1. #include <bits/stdc++.h>
2. using namespace std;
3. string grid[12];
4. bool vis[12][12];
5. int dis[12][12];
6. int dx[] = {0, 0, +1, -1};
7. int dy[] = {+1, -1, 0, 0};
8. int n;
9. bool valid(int x, int y, char ch){
10.     if(x<0 || x == n || y<0||y == n || grid[x][y] == '#') return false;
11.     else if(grid[x][y]>= 'A'&& grid[x][y]<= 'Z' && grid[x][y]  > ch+1) return false;
12.     return true;
13. }
14. int bfs(char ch, int x, int y){
15.     list< pair<int, int> >q;
16.     q.push_back(make_pair(x, y));
17.     vis[x][y]= true;
18.     dis[x][y] = 0;
19.     while(!q.empty()){
20.         int fromx = q.front().first;
21.         int fromy = q.front().second;
22.         vis[fromx][fromy] = true;
23.         q.pop_front();
24.         for(int i = 0; i < 4; i++){
25.             int tox = fromx + dx[i];
26.             int toy = fromy + dy[i];
27.             if(!valid(tox, toy, ch)) continue;
28.             if(vis[tox][toy]) continue;
29.             vis[tox][toy] = true;
30.             q.push_back(make_pair(tox, toy));
31.             dis[tox][toy] = dis[fromx][fromy] + 1;
32.             if(grid[tox][toy] == ch+1) return dis[tox][toy];
33.         }
34.     }
35.     return -1;
36. }
37. int main(){
38.     int ts;
39.     scanf("%d", &ts);
40.     for(int p = 1; p <= ts; p++){
41.     memset(vis, false, sizeof(vis));
42.     memset(dis, false, sizeof(dis));
43.     scanf("%d", &n);
44.     int co = 0;
45.     pair<int,int> positions[26];
46.     for(int i = 0; i <n; i++){
47.         //scanf("%s", grid[i]);
48.         cin>>grid[i];
49.         for(int j = 0; j <grid[i].size(); j++){
50.             if(grid[i][j]>= 'A' && grid[i][j]<= 'Z'){
51.                 positions[grid[i][j]-'A'].first = i;
52.                 positions[grid[i][j]-'A'].second = j;
53.                 co++;
54.             }
55.         }
56.     }
57.     int sum = 0;
58.     for(int i = 0; i <co-1; i++){
59.         int val = bfs('A'+i, positions[i].first, positions[i].second);
60.         if(val == -1) {
61.             sum = -1;
62.             break;
63.         }
64.         sum+= val;
65.         memset(vis, false, sizeof(vis));
66.         memset(dis, false, sizeof(dis));
67.        
68.     }
69.     if(sum == -1) printf("Case %d: Impossible\n", p);
70.     else printf("Case %d: %d\n",p, sum);
71.     }
72.     return 0;
73. }
74.  

Lightoj 1197 - Help Hanzo

http://lightoj.com/volume_showproblem.php?problem=1197

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define maxx 100005
4. bitset<maxx>vis;
5.  
6. vector<int>prime;
7.  
8. void sieve()
9. {
10.  
11.     int x=maxx/2, y=sqrt(maxx)/2;
12.     for(int i=1;i<=y;i++)
13.     {
14.         if(vis[i])
15.         {
16.             for(int j=(i*(i+1))*2;j<=x;j+=(2*i)+1)
17.                 vis[j]=1;
18.         }
19.     }
20.     prime.pb(2);
21.     for(int i=3;i<maxx;i+=2)
22.         if(vis[i/2]==0)
23.             prime.pb(i);
24. }
25.  
26. int segmented_sieve(int a, int b){
27.     vis=0;
28.     if(b<2) return 0;
29.     if(a<2) a=2;
30.     int xx=sqrt((double)b)+1;
31.     for(ll i=0;i<SZ(prime) && prime[i]<=xx;i++){
32.         ll j=(a/prime[i])*prime[i];
33.         if(j <a) j+=prime[i];
34.         if(j<(ll)(prime[i]+prime[i])) j=prime[i]+prime[i];
35.         for(;j<=b;j+=prime[i])
36.             vis[j-a]=1;
37.     }
38.     int cnt=0;
39.     for(ll i=a;i<=b;i++)
40.         if(vis[i-a]==0) cnt++;
41.     return cnt;
42. }
43.  
44. int main()
45. {
46.  
47.      ///freopen("in.txt","r",stdin);
48.     ///freopen("out.txt","w",stdout);
49.     sieve();
50.     int t;
51.     sf(t);
52.     TEST_CASE(t)
53.     {
54.         ll a,b;
55.         sffl(a,b);
56.         PRINT_CASE;
57.         printf("%d\n",segmented_sieve(a,b));
58.     }
59.     return 0;
60. }

Lightoj 1175 - Jane and the Frost Giants

http://lightoj.com/volume_showproblem.php?problem=1175

1. #include <bits/stdc++.h>
2. using namespace std; 
3. const int fx[]={+1,-1,+0,+0};
4. const int fy[]={+0,+0,+1,-1};
5. char graph[201][201];
6. int dj[201][201];
7. int df[201][201];
8. bool visit[201][201];
9.  
10. int r,c;
11. vector<pii>fdata;
12. pii pointj;
13.  
14. bool testf(pii tmp)
15. {
16.     if(tmp.ff<0 || tmp.ff>=r || tmp.ss<0 || tmp.ss>=c || visit[tmp.ff][tmp.ss] || graph[tmp.ff][tmp.ss]!='.')
17.         return 0;
18.     return 1;
19. }
20.  
21. bool testj(pii tmp)
22. {
23.     if(tmp.ff<0 || tmp.ff>=r || tmp.ss<0 || tmp.ss>=c || visit[tmp.ff][tmp.ss] || graph[tmp.ff][tmp.ss]!='.')
24.         return 0;
25.     return 1;
26. }
27.  
28. void bfsf()
29. {
30.     loop(i,r+1) loop(j,c+1)
31.     {visit[i][j]=0;df[i][j]=inf;}
32.  
33.     queue<pii>Q;
34.     pii u,v;
35.     for(int i=0;i<SZ(fdata);i++)
36.     {
37.         u=fdata[i];
38.         df[u.ff][u.ss]=0;
39.         Q.push(u);
40.         visit[u.ff][u.ss]=1;
41.     }
42.     while(!Q.empty())
43.     {
44.         u=Q.front();
45.         Q.pop();
46.         loop(i,4)
47.         {
48.             v.ff=u.ff+fx[i];
49.             v.ss=u.ss+fy[i];
50.             if(testf(v))
51.             {
52.                 visit[v.ff][v.ss]=1;
53.                 df[v.ff][v.ss]=df[u.ff][u.ss]+1;
54.                 Q.push(v);
55.             }
56.         }
57.     }
58. }
59.  
60. int bfsj(pii src)
61. {
62.     loop(i,r+1) loop(j,c+1)
63.        {
64.          visit[i][j]=0;
65.          dj[i][j]=inf;
66.        }
67.     visit[src.ff][src.ss]=1;
68.     pii u,v;
69.     dj[src.ff][src.ss]=0;
70.  
71.     queue<pii>Q;
72.     Q.push(src);
73.     while(!Q.empty())
74.     {
75.         u=Q.front();
76.         Q.pop();
77.         if(u.ff==0 || u.ff==r-1 || u.ss==0 || u.ss==c-1)
78.             return dj[u.ff][u.ss];
79.         loop(i,4)
80.         {
81.             v.ff=u.ff+fx[i];
82.             v.ss=u.ss+fy[i];
83.             if(testj(v) && (df[v.ff][v.ss] > dj[u.ff][u.ss]+1))
84.             {
85.                 visit[v.ff][v.ss]=1;
86.                 dj[v.ff][v.ss]=dj[u.ff][u.ss]+1;
87.                 Q.push(v);
88.             }
89.         }
90.     }
91.     return -1;
92. }
93.  
94.  
95. int main()
96. {
97.     ///freopen("in.txt","r",stdin);
98.     ///freopen("out.txt","w",stdout);
99.     int t;
100.     sf(t);
101.     TEST_CASE(t)
102.     {
103.         sff(r,c);
104.         loop(i,r) loop(j,c)
105.         {
106.             cin>>graph[i][j];
107.             if(graph[i][j]=='J')
108.                 pointj.ff=i,pointj.ss=j;
109.             else if(graph[i][j]=='F')
110.                 fdata.pb(MP(i,j));
111.         }
112.  
113.         bfsf();
114.         int ans=bfsj(pointj);
115.         PRINT_CASE;
116.         if(ans==-1)
117.             pf("IMPOSSIBLE\n");
118.         else
119.             pf("%d\n",ans+1);
120.         fdata.clear();
121.     }
122.     return 0;
123. }