#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<
T,
null_type,
less<T>, // use less_equal to use as multiset without erase operation
rb_tree_tag,
tree_order_statistics_node_update>;
// gives the number of keys with value strictly less than x
#define lesscount(x) order_of_key(x)
// gives the iterator to kth element (starting from 0)
#define kthiterator(x) find_by_order(x)
#define clock_starts() clock_t begin = clock()
#define clock_ends() clock_t end = clock()
#define print_running_time() double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC; \
printf("Elapsed Time : %.10f second(s)\n", elapsed_secs)
#define readfile(s) freopen(s, "r", stdin)
#define writefile(s) freopen(s, "w", stdout)
#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) v.begin(), v.end()
#define cin_cout_is_cool ios_base::sync_with_stdio(false); cin.tie(NULL)
#define printBinary(n) cout << #n << " = " << bitset<64>(n) << endl
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'
#define cin(n) scanf("%d", &n)
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
inline int myrand(int l, int r) {
int ret = rand(); ret <<= 15; ret ^= rand();
if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
return ret;
}
typedef pair<int, int> ii;
template<typename T> using min_pq =
priority_queue<T, vector<T>, greater<T> >;
template<typename T>T max(T a_,T b_,T c_) { return max(a_,max(b_,c_)); }
template<typename T>T min(T a_,T b_,T c_) { return min(a_,min(b_,c_)); }
template<typename T>T min(T a_,T b_,T c_, T d_) { return min(min(a_, b_),min(b_,c_)); }
template<typename T>T max(T a_,T b_,T c_, T d_) { return max(max(a_, b_),max(b_,c_)); }
//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};
template<typename T> inline T ceil(T num, T d)
{ return (T)(num/d) + (num%d>(T)0 ? (T)1 : (T)0); }
#define block_no(idx) (idx/BLOCK_SIZE)
#define block_starting(idx) (block_no(idx)*BLOCK_SIZE)
#define block_ending(idx) (min(n, block_no(idx)*BLOCK_SIZE+BLOCK_SIZE-1))
#define block_rank(idx) (idx%BLOCK_SIZE)
const int maxn = 516;
#define lg 9
#define node(x, y) ((x<<lg)|y)
vector<pair<int, int> > v[node(500, 500)+10];
int e[maxn*maxn], vis[maxn*maxn], n, m;
char s[maxn][maxn];
void print(ii oo) {
cout<<"("<<(oo.first>>lg)<<", "<<(oo.first&((1<<lg)-1))<<", "<<oo.second<<")";
}
int dfs(int now, int to) { // to check if connected
if(now == to) return 1;
vis[now] = 1;
for(auto x : v[now]) {
int b = x.first;
if(!vis[b]) {
int ret = dfs(b, to);
if(ret) return ret;
}
} return 0;
}
int solve(int C, int F) { // dijkstra
min_pq<ii> pq;
MEMSET(vis, 0);
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) e[node(i,j)] = 1e9;
e[C] = 0;
pq.push(ii(0,C));
while(!pq.empty()) {
int u = pq.top().second; pq.pop();
if(vis[u]) continue;
vis[u] = 1;
for(auto b : v[u]) {
int x = b.first, w = b.second;
if(e[u]+w < e[x]) {
e[x] = e[u]+w;
pq.push(ii(e[x], x));
}
}
}
return e[F];
}
int main () {
//readfile("input.in");
cin(n), cin(m);
for(int i=1; i<=n; i++) scanf("%s", s[i]+1);
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(s[i][j] == '#') continue;
int u, d, l, r;
for(int k=i-1; k>=0; k--) { // up
if(s[k][j] == '#') {
u = k+1; break;
}
}
for(int k=i+1; k<=n; k++) { // down
if(s[k][j] == '#') {
d = k-1; break;
}
}
for(int k=j-1; k>=0; k--) { // left
if(s[i][k] == '#') {
l = k+1; break;
}
}
for(int k=j+1; k<=m; k++) { // right
if(s[i][k] == '#') {
r = k-1; break;
}
}
//cout<<"("<<i<<", "<<j<<")"<<" :: "<<u<<' '<<d<<' '<<l<<' '<<r<<endl;
if(u!=i) v[node(i,j)].push_back(ii(node(u,j), min(i-u, 1+j-l, 1+r-j, 1+d-i))); // up
if(d!=i) v[node(i,j)].push_back(ii(node(d,j), min(d-i, 1+j-l, 1+r-j, 1+i-u))); // down
if(l!=j) v[node(i,j)].push_back(ii(node(i,l), min(j-l, 1+i-u, 1+d-i, 1+r-j))); // left
if(r!=j) v[node(i,j)].push_back(ii(node(i,r), min(r-j, 1+i-u, 1+d-i, 1+j-l))); // right
if(i-u > 1) v[node(i,j)].push_back(ii(node(i-1,j), 1)); // up
if(d-i > 1) v[node(i,j)].push_back(ii(node(i+1,j), 1)); // down
if(j-l > 1) v[node(i,j)].push_back(ii(node(i,j-1), 1)); // left
if(r-j > 1) v[node(i,j)].push_back(ii(node(i,j+1), 1)); // right
//cout<<"["<<i<<", "<<j<<"]"<<" :: ";
//for(auto b : v[node(i,j)]) print(b), cout<<", "; cout<<endl;
}
}
int C, F;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(s[i][j] == 'C') C = node(i,j);
else if(s[i][j] == 'F') F = node(i,j);
}
}
int ret = dfs(C,F);
if(!ret) {
cout<<"nemoguce"<<endl;
}
else {
cout<<solve(C,F)<<endl;
}
return 0;
}
Compilation message
portal.cpp: In function 'int main()':
portal.cpp:143:48: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
if(i-u > 1) v[node(i,j)].push_back(ii(node(i-1,j), 1)); // up
^
portal.cpp:67:22: note: in definition of macro 'node'
#define node(x, y) ((x<<lg)|y)
^
portal.cpp:144:48: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
if(d-i > 1) v[node(i,j)].push_back(ii(node(i+1,j), 1)); // down
^
portal.cpp:67:22: note: in definition of macro 'node'
#define node(x, y) ((x<<lg)|y)
^
portal.cpp:145:50: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
if(j-l > 1) v[node(i,j)].push_back(ii(node(i,j-1), 1)); // left
^
portal.cpp:67:29: note: in definition of macro 'node'
#define node(x, y) ((x<<lg)|y)
^
portal.cpp:146:50: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
if(r-j > 1) v[node(i,j)].push_back(ii(node(i,j+1), 1)); // right
^
portal.cpp:67:29: note: in definition of macro 'node'
#define node(x, y) ((x<<lg)|y)
^
portal.cpp:112:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
cin(n), cin(m);
^
portal.cpp:112:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
portal.cpp:113:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1; i<=n; i++) scanf("%s", s[i]+1);
^
portal.cpp:163:18: warning: 'F' may be used uninitialized in this function [-Wmaybe-uninitialized]
cout<<solve(C,F)<<endl;
^
portal.cpp:163:18: warning: 'C' may be used uninitialized in this function [-Wmaybe-uninitialized]
portal.cpp:142:53: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(r!=j) v[node(i,j)].push_back(ii(node(i,r), min(r-j, 1+i-u, 1+d-i, 1+j-l))); // right
^
portal.cpp:141:53: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(l!=j) v[node(i,j)].push_back(ii(node(i,l), min(j-l, 1+i-u, 1+d-i, 1+r-j))); // left
^
portal.cpp:140:53: warning: 'd' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(d!=i) v[node(i,j)].push_back(ii(node(d,j), min(d-i, 1+j-l, 1+r-j, 1+i-u))); // down
^
portal.cpp:139:53: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
if(u!=i) v[node(i,j)].push_back(ii(node(u,j), min(i-u, 1+j-l, 1+r-j, 1+d-i))); // up
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10372 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
10372 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
10372 KB |
Output is correct |
| 2 |
Correct |
0 ms |
10372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
10372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
11428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
13012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
89 ms |
20108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
136 ms |
21288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
139 ms |
24824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
