mehmet's blog

By mehmet, 10 years ago, In English

Hi, I am trying to solve Drazil and Tiles problem. But in the 7th input which is

3 3
.*.
...
.*.

I am getting run time error. When I try that input in my PC, it works well and gives correct answer. I also tried many other inputs in that question and my code works correctly for all input. That is my code and I will really appreciate if you can help me.

#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>

#define MAX 2002
#define FOR(i,j,k) for(int i=j;i<k;i++)
#define pint pair<int,int>
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second

using namespace std;

int N,M;
string A[MAX];
int dir[4][2]={-1,0,1,0,0,1,0,-1};
int K[MAX][MAX];
int finish;

void read(){
	
	cin >> N >> M;
	FOR(i,0,N){
		cin >> A[i];
		FOR(j,0,M)
			finish += (A[i][j] == '*'? 1:0 );
	}
}

int findNumberofAdj(int i,int j){

	int adj = 0;
	FOR(y,0,4){
		int a = dir[y][0]+i, b = dir[y][1]+j;
		if(a>=0 && a<N && b>=0 && b<M && A[a][b]=='.')
			adj++;
	}
	return adj;
}

pint findAdj(int i,int j){
	FOR(y,0,4){
		int a = dir[y][0]+i, b = dir[y][1]+j;
		if(a>=0 && a<N && b>=0 && b<M && A[a][b]=='.')
			return mp(a,b);
	}
}

void mark(pint a,pint b){
	if(a.se-b.se==1) {A[a.fi][a.se] = '>';A[b.fi][b.se] = '<';}
	if(a.se-b.se==-1) {A[a.fi][a.se] = '<';A[b.fi][b.se] = '>';}
	if(a.fi-b.fi==1) {A[a.fi][a.se] = 'v';A[b.fi][b.se] = '^';}
	if(a.fi-b.fi==-1) {A[a.fi][a.se] = '^';A[b.fi][b.se] = 'v';}
}

void solve(){
	queue< pint > q;
	FOR(i,0,N)
		FOR(j,0,M)
			if(A[i][j] == '.' && findNumberofAdj(i,j)==1)
				q.push(mp(i,j));

	while(!q.empty()){
		pint x = q.front();
		q.pop();

		pint adj = findAdj(x.fi,x.se);
		if(K[x.fi][x.se] || K[adj.fi][adj.se]) continue;
		K[x.fi][x.se] = K[adj.fi][adj.se] = 1;
		finish+=2;
		
		mark(x,adj);
		FOR(y,0,4){
			int a = dir[y][0]+x.fi, b = dir[y][1]+x.se;
			if(findNumberofAdj(a,b)==1 && A[a][b] == '.' && !K[a][b]){
				q.push(mp(a,b));
			}
			a = dir[y][0]+adj.fi; b = dir[y][1]+adj.se;
			if(findNumberofAdj(a,b)==1 && A[a][b] == '.' && !K[a][b]){
				q.push(mp(a,b));
			}
		}
	}

	if(finish != N*M)
		cout << "Not unique" << endl;
	else
		FOR(i,0,N)
			cout << A[i] << endl;
}

int main(){

	read();
	solve();
	return 0;	
}

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it