#2327573

Solution for 1144: Curling 2.0 by claw88

Source Code Status Test Cases
    Policy: public     Reviewed: 17    
00.13 sec    3100 KB    96 lines     1895 bytes    2017-05-20 03:12
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec; typedef pair<int, int> pi;
int dd[] = { 0, 1, 0, -1, 0 };
char ban[25][25];// tmp[25][25];
int sx, sy, gx, gy;
int ans = 20;
int W, H;
void dfs(char C[25][25], int depth, int ty, int tx, int before)
{
  //printf("ty=%d tx=%d\n",ty,tx );
  if(depth == 10)return;
  for(int r =0; r < 4; r++)
    {
      //if(before == r)continue;
      char tmp[25][25];
     	for(int i = 0; i < H; i++)
     	{
     		for(int j = 0; j < W; j++)
     		{
     			tmp[i][j]=C[i][j];
     		}
     	}
      int y = ty, x = tx;
      if(y+dd[r]<0||y+dd[r]>=H||x+dd[r+1]<0||x+dd[r+1]>=W)continue;
      if(tmp[y+dd[r]][x+dd[r+1]]=='1')continue;
      int flag = 0;
      while(true)
	{
	  y += dd[r];
	  x += dd[r + 1];
	  if(y< 0||y>=H||x<0||x>=W)break;
	  if(y == gy && x == gx)
	    {
	    	//printf("%d %d karagoal\n", ty, tx);
	      ans = min(ans, depth+1);
	    }
	  if(tmp[y][x]=='1')
	    {
	      flag = 1;
	      tmp[y][x] = '0';
	      y -= dd[r];
	      x -= dd[r+1];
	      break;
	    }
	}
      if(flag)
	{
		//printf("%d %d kara %d %d  %d\n",ty, tx, y, x, r);
	  dfs(tmp, depth+1, y, x,(r+2)%4);
	}
      
    }
 
}


int main()
{
  while(true)
    {
      scanf("%d%d", &W, &H);
      //printf("now%d %d\n",W, H);
      if(W == 0 && H == 0)break;
      for(int i = 0; i < H; i++)
	{
	  for(int j = 0; j < W; j++)
	    {
	      cin >> ban[i][j];
	      // scanf("%c", &ban[i][j]);
	      if(ban[i][j]=='2')
		{
		  sy=i;
		  sx=j;
		}
	      if(ban[i][j]=='3')
		{
		  gy=i;
		  gx=j;
		}
		//cout << ban[i][j];
	    }
	    //cout << endl;
	}
      // printf("jj\n");
      ans = 20;
      dfs(ban, 0, sy, sx, -1);
      if(ans == 20)printf("-1\n");
      else printf("%d\n",ans);
			  
    }
  return 0;
}

Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 1/1 C++ CPU: 00.13 sec Memory: 3100 KB Length: 1895 B 2017-05-20 03:12 2017-05-20 03:12
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 00.13 sec 3100 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags