/*
user: php
time: 0.004 sec
link: http://www.lightoj.com/volume_showproblem.php?problem=1012
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
#define MAXX 21
using namespace std;
int dirx[] = {-1, 1, 0, 0};
int diry[] = {0, 0, -1, 1};
char graph[MAXX][MAXX];
bool visited[MAXX][MAXX];
int width, height;
struct DATA{
int x, y;
void set(int i, int j)
{
x = i;
y = j;
}
};
int bfs(DATA u)
{
mem(visited, false);
queue<DATA> Q;
DATA v;
Q.push(u);
visited[u.x][u.y] = true;
int total = 1;
while( ! Q.empty() )
{
u = Q.front();
loop(i, 4)
{
v.set(u.x+dirx[i], u.y + diry[i]);
if(-1 < v.x && v.x < width && -1 < v.y && v.y < height && graph[v.y][v.x]=='.' && !visited[v.x][v.y] )
{
visited[v.x][v.y] = true;
Q.push(v);
total++;
}
}
Q.pop();
}
return total;
}
int main()
{
DATA point;
int kases, kaseno = 0;
getint(kases);
while(kases--)
{
getint(width); getint(height);
loop(i, height)
{
scanf("%s", graph[i]);
loop(j, width)
{
if(graph[i][j] == '@')
{
point.set(j, i);
}
}
}
printf("Case %d: %d\n", ++kaseno, bfs(point));
}
return 0;
}
Monthly Archives: January 2013
(UVa) 103 – Stacking Boxes
0
/*
user: php
time: 0.008 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=39
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
using namespace std;
struct DATA{
int ara[11];
char pos;
};
DATA boxes[31];
int number_of_boxes, count_dimentions;
int dir[31];
int dp[31];
bool compare(DATA a, DATA b)
{
loop(i, count_dimentions)
{
if(a.ara[i] > b.ara[i])
{
return false;
}
}
return true;
}
bool test(DATA a, DATA b)
{
loop(i, count_dimentions)
{
if(a.ara[i] >= b.ara[i])
{
return false;
}
}
return true;
}
int longest(int u)
{
int &ret = dp[u];
if( ret != -1) return ret;
int maxi = 0;
for(int v=u+1; v<number_of_boxes; v++)
{
if(test(boxes[u], boxes[v]))
{
if(maxi < longest(v))
{
maxi = longest(v);
dir[u] = v;
}
}
}
return ret = maxi + 1;
}
int main()
{
int LIS;
int from;
while(scanf("%d %d", &number_of_boxes, &count_dimentions) == 2)
{
loop(i, number_of_boxes)
{
boxes[i].pos = i;
loop(j, count_dimentions)
{
getint(boxes[i].ara[j]);
}
}
loop(i, number_of_boxes)
{
sort(boxes[i].ara, boxes[i].ara+count_dimentions);
}
sort(boxes, boxes+number_of_boxes, compare);
mem(dp, -1);
mem(dir, -1);
LIS = -1;
loop(i, number_of_boxes)
{
if(longest(i) > LIS)
{
LIS = longest(i);
from = i;
}
}
printf("%d\n", LIS);
while(dir[from] != -1)
{
printf("%d ", boxes[from].pos+1);
from = dir[from];
}
printf("%d\n", boxes[from].pos+1);
}
return 0;
}
(lightOj) 1002 – Country Roads
0
/*
user: php
time: 0.276 sec
link: http://www.lightoj.com/volume_showproblem.php?problem=1002
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<stack>
#include<vector>
#include<queue>
#define loop(i, n) for(int i=0; i<n; i++)
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define SZ size()
#define mem(ara, val) memset(ara, val, sizeof(ara))
#define pi acos(-1.0)
#define INF 1<<29
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define pb push_back
#define ll long long
#define geti(n) scanf("%d",&n)
#define MAXX 505
using namespace std;
int weight[MAXX][MAXX];
vector<int>node[MAXX];
int dist[MAXX];
struct DATA{
int city, dist;
};
struct compare{
bool operator()(DATA a, DATA b)
{
return a.dist > b.dist;
}
};
void dijkstra(int source)
{
int len;
priority_queue<DATA, vector<DATA>, compare >Q;
DATA u, v;
u.city = source;
u.dist = 0;
dist = 0;
Q.push(u);
while( !Q.empty() )
{
u = Q.top(); Q.pop();
if(u.dist != dist[u.city]) continue;
len = node[u.city].SZ;
loop(i, len)
{
v.city = node[u.city][i];
v.dist = max(u.dist, weight[u.city][v.city]);
if(v.dist < dist[v.city])
{
dist[v.city] = v.dist;
Q.push(v);
}
}
}
}
int main()
{
int kases, kaseno = 0;
int cities, roads;
geti(kases);
int p, q, w;
int source;
while(kases--)
{
loop(i, MAXX)
{
node[i].clear();
dist[i] = INF;
loop(j, MAXX)
{
weight[i][j] = INF;
weight[j][i] = INF;
}
}
geti(cities);
geti(roads);
loop(i, roads)
{
geti(p); geti(q); geti(w);
if(w < weight[p][q])
{
weight[p][q] = w;
weight[q][p] = w;
node[p].pb(q);
node[q].pb(p);
}
}
geti(source);
dijkstra(source);
printf("Case %d:\n", ++kaseno);
loop(i, cities)
{
if(dist[i] == INF)
printf("Impossible\n");
else
printf("%d\n", dist[i]);
}
}
return 0;
}
(LightOj) 1337 – The Crystal Maze
0In this code, read() = freopen() isn’t working properly… I don’t know why?? đĻ
/*
user: php
time: 0.128 sec
link: http://www.lightoj.com/volume_showproblem.php?problem=1337
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<vector>
using namespace std;
#define loop(i, n) for(int i=0; i<n; i++)
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define pb push_back
#define mem(a, v) memset(a, v, sizeof(a))
#define SZ size()
#define pi acos(-1.0)
#define INF 1<<29
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define ll long long
#define mod(a) (a>0?(a):(-a))
#define get(n) scanf("%d", &n)
#define MAXX 505
#define debug cout<<"ok"
int count_row, count_column;
char graph[MAXX][MAXX];
int* dp[MAXX][MAXX];
int value[MAXX][MAXX];
bool visited[MAXX][MAXX];
int p, q;
void dfs(int x, int y)
{
if(x<0 || x == count_row || y<0 || y == count_column || visited[x][y] || graph[x][y] == '#') return;
dp[x][y] = &value[p][q];
visited[x][y] = true;
if(graph[x][y] == 'C')
{
value[p][q]++;
}
dfs(x+1, y);
dfs(x-1, y);
dfs(x, y-1);
dfs(x, y+1);
return;
}
int main()
{
int kases, kaseno = 0;
int query;
get(kases);
while(kases--)
{
mem(visited, false);
get(count_row);
get(count_column);
get(query);
loop(i, count_row)
{
scanf("%s", graph[i]);
}
printf("Case %d:\n", ++kaseno);
loop(i, query)
{
get(p);
get(q);
p--;
q--;
if(graph[p][q] == '#')
{
printf("0\n");
continue;
}
if( ! visited[p][q] )
{
value[p][q] = 0;
dfs(p, q);
}
printf("%d\n", *(dp[p][q]));
}
}
return 0;
}
(UVa) 116 – Unidirectional TSP
0
/*
user: php
time: 0.136 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=52
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
using namespace std;
template<typename T>
T min(T a, T b, T c)
{
a = min(a, b);
a = min(a, c);
return a;
}
int countrow, countcolumn;
int value[12][102];
ll dp[12][102];
int dir[12][102];
int fix(int n)
{
if(n==-1)
{
return countrow - 1;
}
else if(n == countrow)
{
return 0;
}
else
{
return n;
}
}
ll rec(int row, int column)
{
row = fix(row);
ll &ret = dp[row][column];
if(ret != -1) return ret;
ret = value[row][column];
if(column + 1 < countcolumn)
{
ll p, q, r;
p = rec(row-1, column+1);
q = rec(row, column+1);
r = rec(row+1, column+1);
if(p < q || (p==q && fix(row-1) <= fix(row)))
{
if(p < r || (p==r && fix(row-1) <= fix(row+1) ))
{
dir[row][column] = fix(row-1);
}
else
{
dir[row][column] = fix(row+1);
}
}
else
{
if(q < r || (q==r && fix(row) <= fix(row+1)))
{
dir[row][column] = row;
}
else
{
dir[row][column] = fix(row+1);
}
}
ret += min(p, q, r);
}
return ret;
}
int main()
{
//read();
ll minimum;
int start;
int t;
while(scanf("%d %d", &countrow, &countcolumn) == 2)
{
loop(i, countrow)
{
loop(j, countcolumn)
{
getint(value[i][j]);
dp[i][j] = -1;
}
}
minimum = INF;
loop(i, countrow)
{
if(rec(i, 0) < minimum)
{
minimum = dp[i][0];
start = i;
}
}
t = 0;
do{
printf("%d", start+1);
start = dir[start][t++];
}while( t < countcolumn && printf(" "));
printf("\n%lld\n", minimum);
}
return 0;
}
(LightOj) 1003 – Drunk
0
/*
user: php
time: 0.244 sec
link: http://lightoj.com/volume_showproblem.php?problem=1003
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<map>
#include<stack>
#include<queue>
#include<string>
#include<vector>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define mem(a, v) memset(a, v, sizeof(a))
#define PI acos(-1.0)
#define INF 1<<29
#define SZ size()
#define all(v) v.begin(), v.end()
#define pb(a) push_back(a)
#define ll long long
#define READ() freopen("input.txt", "r", stdin)
#define WRITE() freopen("output.txt", "w", stdout)
#define geti(n) scanf("%d", &n)
#define getii(a, b) scanf("%d %d", &a, &b)
using namespace std;
int main()
{
int kases, query, kaseno = 0;
string a, b;
map<string, vector<string> > mp;
map<string, int> weight;
map<string, bool> all;
map<string, bool>::iterator it;
vector<string> *v;
int *p;
bool drunk;
vector<string>zero;
geti(kases);
while(kases--)
{
mp.clear();
weight.clear();
zero.clear();
all.clear();
geti(query);
loop(i, query)
{
cin>>a>>b;
all[a] = 0;
all[b] = 0;
mp[a].pb(b);
weight[b]++;
}
for(it = all.begin(); it != all.end(); it++)
{
a = it->first;
if(weight[a] == 0)
zero.pb(a);
}
loop(i, zero.SZ)
{
a = zero[i];
v = &mp[a];
loop(j, v->SZ)
{
b = (*v)[j];
p = &weight[b];
(*p)--;
if((*p) == 0)
{
zero.pb(b);
}
}
}
drunk = true;
for(it = all.begin(); it != all.end(); it++)
{
a = it->first;
if(weight[a] != 0)
{
drunk = false;
break;
}
}
if(drunk)
{
printf("Case %d: Yes\n", ++kaseno);
}
else
{
printf("Case %d: No\n", ++kaseno);
}
}
return 0;
}
(UVa) 10918 – Tri Tiling
0
/*
user: php
time: 0.008 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1859
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<stack>
#include<stack>
#include<queue>
#include<string>
#include<sstream>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size
#define all(v) v.begin(), v.end()
#define mod(a) ((a) > 0 ? (a) : -(a))
#define pi acos(-1.0)
#define INF 1<<29
#define READ() freopen("input.txt", "r", stdin)
#define WRITE() freopen("output.txt", "w", stdout)
#define mem(a, val) memset(a, val, sizeof(a))
using namespace std;
int g_dp[31];
int f_dp[31];
int g(int n);
int f(int n)
{
if(f_dp[n] != -1) return f_dp[n];
return f_dp[n] = f(n-2) + 2 * g(n-1);
}
int g(int n)
{
if(g_dp[n] != -1) return g_dp[n];
return g_dp[n] = f(n-1) + g(n-2) ;
}
int main()
{
FOR(i, 2, 31)
{
g_dp[i] = f_dp[i] = -1;
}
g_dp[0] = f_dp[1] = 0;
g_dp[1] = f_dp[0] = 1;
int n;
while(getint(n) && n > -1 )
{
if(n % 2 == 1)
{
printf("0\n");
continue;
}
printf("%d\n", f(n));
}
return 0;
}
(UVa) 10452 – Marcus
0
/*
user: php
time: 0.008 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1393
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
using namespace std;
int parent[8][8];
string graph[8];
int level, len;
int kases;
int pos;
char possible[] = "IEHOVA@";
bool visited[8][8];
bool check(char c)
{
loop(i, 7)
{
if(possible[i] == c)
{
return true;
}
}
return false;
}
void dfs(int l, int pos)
{
if( pos+1 < len)
{
if(!visited[l][pos+1] && check(graph[l][pos+1]))
{
visited[l][pos+1] = true;
parent[l][pos+1] = 4; //left;
if(graph[l][pos+1] != '@')
{
dfs(l, pos+1);
}
else
{
return;
}
}
}
if( 0 < pos )
{
if(!visited[l][pos-1] &&check(graph[l][pos-1]))
{
visited[l][pos-1] = true;
parent[l][pos-1] = 6; //right;
if(graph[l][pos-1] != '@')
{
dfs(l, pos-1);
}
else
{
return;
}
}
}
if(l+1 < level)
{
if(!visited[l+1][pos] && check(graph[l+1][pos]))
{
visited[l+1][pos] = true;
parent[l+1][pos] = 2; // forward;
if(graph[l+1][pos] != '@')
{
dfs(l+1, pos);
}
else
{
return;
}
}
}
}
int main()
{
cin>>kases;
while(kases--)
{
mem(visited, false);
cin>>level>>len;
for(int i=0; i<level; i++)
{
cin>>graph[i];
}
loop(i, len)
{
if(graph[0][i] == '#')
{
pos = i;
break;
}
}
dfs(0, pos);
loop(i, len)
{
if(graph[level-1][i] == '@')
{
pos = i;
break;
}
}
int i=level - 1;
do
{
if(parent[i][pos] == 2)
{
i--;
printf("forth");
}
else if(parent[i][pos] == 4)
{
printf("left");
pos--;
}
else
{
printf("right");
pos++;
}
}while(graph[i][pos] != '#' && printf(" "));
printf("\n");
}
return 0;
}
(UVa) 11060 – Beverages
0
/*
user: php
time: 0.020 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2001
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#define getint(a) scanf("%d", &a)
#define loop(i, n) for(int i=0; i<n; i++)
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define pb(a) push_back(a)
#define SZ size()
using namespace std;
map<string, int> pos;
struct compare{
bool operator () (string a, string b)
{
return pos[a] > pos[b];
}
};
vector<string>beverages;
map<string, vector<string> > graph;
map<string, int>weight;
priority_queue<string, vector<string>, compare> zeroWeight;
vector<string>list;
int main()
{
string p, q;
int *point;
int kaseno = 0;
int bevarage_number, connections;
while(getint(bevarage_number) == 1)
{
weight.clear();
while(zeroWeight.SZ)
{
zeroWeight.pop();
}
list.clear();
beverages.clear();
graph.clear();
loop(i, bevarage_number)
{
cin>>p;
beverages.pb(p);
pos[p] = i;
}
getint(connections);
loop(i, connections)
{
cin>>p;
cin>>q;
graph[p].pb(q);
weight[q]++;
}
loop(i, bevarage_number)
{
p = beverages[i];
if(weight[p] == 0)
{
zeroWeight.push(p);
}
}
loop(i, bevarage_number)
{
p = zeroWeight.top();
zeroWeight.pop();
list.pb(p);
loop(j, graph[p].SZ)
{
q = graph[p][j];
point = &weight[q];
(*point)--;
if(*point == 0)
{
zeroWeight.push(q);
}
}
}
printf("Case #%d: Dilbert should drink beverages in this order: %s", ++kaseno, list[0].c_str());
FOR(i, 1, bevarage_number)
{
cout<<" "<<list[i];
}
printf(".\n\n");
}
}
(UVa) 10305 – Ordering Tasks
0
/*
user: php
time: 0.008 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1246
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
using namespace std;
vector<int> graph[101];
int weight[101];
vector<int> zeroWeighted;
int main()
{
int n, m;
int p, q;
while(scanf("%d %d", &n, &m) == 2 && (n!=0 || m!=0))
{
loop(i, 101)
{
graph[i].clear();
weight[i] = 0;
zeroWeighted.clear();
}
loop(i, m)
{
getint(p); getint(q);
graph[p].pb(q);
weight[q]++;
}
for(int i=1; i<=n; i++)
{
if(weight[i] == 0)
{
zeroWeighted.pb(i);
}
}
loop(i, zeroWeighted.SZ)
{
p = zeroWeighted[i];
loop(j, graph[p].SZ)
{
q = graph[p][j];
weight[q]--;
if(weight[q] == 0)
{
zeroWeighted.pb(q);
}
}
}
printf("%d", zeroWeighted[0]);
FOR(i, 1, zeroWeighted.SZ)
{
printf(" %d", zeroWeighted[i]);
}
printf("\n");
}
return 0;
}
UnLucky Codes 