DCP - 60 : Holloween Party (Runtime Error)

Dev Skill archived problems can be discussed here.

DCP - 60 : Holloween Party (Runtime Error)

by froghramar » Sun Dec 04, 2016 7:31 pm

I'm getting runtime error. I think it's not because invalid indexing. Can anyone find the reason?

Code: Select all
#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;
const int N = 1005;

struct TT{
   int x, y, w;
   TT(){}
   TT(int X, int Y, int W){
      x = X, y = Y, w = W;
   }
};

class Tcompare{
   public:
   bool operator() (TT p, TT q){
      if(p.w != q.w) return p.w > q.w;
      if(p.x != q.x) return p.x > q.x;
      return p.y > q.y;
   }
};

char s[N][N];
int n, m;
bool visited[N][N];

bool valid(int x, int y){
   return x >= 1 and x <= n and y >= 1 and y <= m;
}

int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

void init(){
   int T;
   scanf("%d",&T);
   for(int t=1; t<=T; t++){
      scanf("%d%d",&n,&m);
      for(int i = 1; i <= n; i++){
         scanf("%s",s[i] + 1);
      }
      priority_queue <TT, vector<TT>, Tcompare> pq;
      memset(visited,0,sizeof(visited));
      pq.push(TT(1,1,0));
      int res = -1;
      while(!pq.empty()){
         TT u = pq.top();
         pq.pop();
         if(visited[u.x][u.y]) continue;
         visited[u.x][u.y] = 1;
         if(u.x == n and u.y == m){
            res = u.w;
            break;
         }
         for(int i = 0; i < 4; i++){
            TT v(u.x + dx[i], u.y + dy[i], u.w);
            if(!valid(v.x, v.y)) continue;
            if(s[u.x][u.y] != s[v.x][v.y]) v.w++;
            if(!visited[v.x][v.y]) pq.push(v);
         }
      }
      printf("Case %d: %d\n",t,res);
   }
}

int main(){
   #ifndef ONLINE_JUDGE
      freopen("input.txt","r",stdin);
      freopen("output.txt","w",stdout);
   #endif
   init();
   return 0;
}
User avatar
 
Posts: 33
Joined: Thu Jul 28, 2016 8:14 am
Location: Amar Ekushey Hall, University of Dhaka

Who is online
Users browsing this forum: No registered users and 1 guest
cron