Owner: sabry_ragab
Source code for: MLASERP - Laser Phones (SPOJ)
Language: C++
Comment: Wrong answer
Who can see this: Anyone who knows its URL

Hide line numbers
/**
 * @Author : sabry_ragab
 */
 
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
 
const double eps = 1e-10;
const int dx[] = { 1, 0, -1, 0, -1, -1, 1, 1 }; //first 4 are top - down - left - right
const int dy[] = { 0, 1, 0, -1 , -1, 1, -1, 1 };
const double pi = acos(-1.0);
const int OO = INT_MAX;
 
#define SZ(x)          (int)x.size()
#define ALL(x)         (x).begin(),(x).end()
#define ALLR(x)        (x).rbegin(),(x).rend()
#define PB( x )         push_back(x)
#define MP(x , y)       make_pair(x,y)
#define rep(i,st,en)    for(int i=st ; i< en; i++)
#define repR(i,st,en)   for(int i=st;i>=en ; i--)
#define fill(v, d)       memset(v, d, sizeof(v))
template<class A, class B> A convert(B x) {stringstream s;s << x;A r;s >> r;return r;}
/**************************************************************/
struct Node{
    pii cur;
    pii perv;
    pii beforePerv;
    int nMirror;
 
    Node(pii cur, pii perv, pii beforePerv, int nMirror){
        this->beforePerv = beforePerv;
        this->cur = cur;
        this->perv = perv;
        this->nMirror = nMirror;
    }
};
const int MAX = 101;
int cost[MAX][MAX];
char grid[MAX][MAX];
int w, h;
 
int bfs(pii cow1Position, pii cow2Position){
 
    rep(i, 0, h){
        rep(j, 0, w){
            cost[i][j] = OO;
        }
    }
 
    queue<Node>q;
    q.push( Node(cow1Position, cow1Position, cow1Position, 0) );
 
    while( !q.empty() ){
        Node node = q.front();
        q.pop();
 
        //invalid cases
        if(node.cur.first >= h || node.cur.first  < 0 ||
                node.cur.second >= w || node.cur.second < 0 ||
                grid[node.cur.first][node.cur.second] == '*'){
            continue;
        }
 
        //check mirror case
        if(abs(node.cur.first - node.beforePerv.first) == 1 &&
                abs(node.cur.second - node.beforePerv.second) == 1){
            node.nMirror++;
        }
 
        if( cost[node.cur.first][node.cur.second] <= node.nMirror ){
            continue;
        }
 
        cost[node.cur.first][node.cur.second] = node.nMirror;
 
        rep(i, 0, 4){
            pii nxt = MP(dx[i] + node.cur.first, dy[i] + node.cur.second);
            q.push(Node(nxt, node.cur, node.perv, node.nMirror) );
        }
 
    }
 
    return cost[cow2Position.first][cow2Position.second];
}
 
/***************************************************************/
int main() {
//freopen("input.txt" , "rt",stdin) ;
//freopen("output.txt", "wt", stdout);
 
    scanf("%d%d", &w, &h);
 
    rep(i, 0, h){
        scanf("%s", grid[i]);
    }
 
    //get cows position
    vector<pii>cow;
 
    rep(i, 0, h){
        rep(j, 0, w){
            if(grid[i][j] == 'C'){
                cow.PB( MP(i, j));
            }
        }
    }
 
    int res = bfs(cow[0], cow[1]);
 
    printf("%d\n", res);
//--------------------------------------------------------//
    return 0;
}