Untitled

mail@pastecode.io avatar
unknown
plain_text
8 days ago
2.3 kB
1
Indexable
Never
#include <iostream>
using namespace std;
struct Point
{
 int hang,cot;
};
Point queue[10000000];
struct Queue
{
 int rear, front;
 Queue()
 {
  rear = front = 0;
 }
 void push(Point a)
 {
  queue[rear] = a;
  rear++;
 }
 Point pop()
 {
  Point a;
  a = queue[front];
  front++;
  return a;
 }
 bool isEmpty()
 {
  if(rear == front) return true;
  else return false;
 }
};
int N,M;
Point vt_do, vt_rong;
int map[3030][3030];
int visit[3030][3030];
int dx[4] = {0,-1,0,1};
int dy[4] = {-1,0,1,0};
void BFS()
{
 Queue Q = Queue();
 Q.push(vt_do);
 visit[vt_do.hang][vt_do.cot] = 1;
 while(!Q.isEmpty())
 {
  Point p = Q.pop();
  for(int i = 0; i<4;i++)
  {
   int h = p.hang + dx[i];
   int c = p.cot + dy[i];
   if(h >= 1 && h <= N && c >= 1 && c <= M && visit[h][c] == 0 && map[h][c] != 0 && map[h][c] != 2)
   {
    visit[h][c] = visit[p.hang][p.cot]+1;
    Point tp;
    tp.hang = h;
    tp.cot = c;
    Q.push(tp);
   }
  }
 }
}
int check_full_map()
{
 int max = 0;
 for(int i = 1; i<= N; i++)
 {
  for(int j = 1; j<= M; j++)
  {
   if(map[i][j] != 0 && visit[i][j] != 0 && map[i][j] != 2)
   {
    if(visit[i][j] > max)
    {
     max = visit[i][j];
    }
   }
   else if(map[i][j] != 0 && visit[i][j] == 0 && map[i][j] != 2)
   {
    return -1;
   }
  }
 }
 return max;
}
int check_day_cell()
{
 int max = 0;
 for(int i = 0; i<4; i++)
 {
  if(visit[vt_rong.hang + dx[i]][vt_rong.cot + dy[i]] == 0)
  {
   return -1;
  }
  else
  {
   if(visit[vt_rong.hang + dx[i]][vt_rong.cot + dy[i]] > max)
   {
    max = visit[vt_rong.hang + dx[i]][vt_rong.cot + dy[i]];
   }
  }
 }
 return max;
}
int main()
{
 //freopen("input.txt","r",stdin);
 int T;
 cin >> T;
 for(int tc = 1; tc <= T; tc++)
 {
  cin >> N >> M;
  cin >> vt_do.hang >> vt_do.cot;
  for(int i = 1; i<=N; i++)
  {
   for(int j = 1;j<=M; j++)
   {
    cin >> map[i][j];
    if(map[i][j] == 2)
    {
     vt_rong.hang = i;
     vt_rong.cot = j;
    }
   }
  }
  for(int i = 1; i<=N; i++)
  {
   for(int j = 1;j<=M; j++)
   {
    visit[i][j] = 0;
   }
  }
  BFS();
  cout << "Case #" << tc << endl;
  int check_full = check_day_cell();
  int full_map = check_full_map();
  if(check_full == -1)
  {
   cout << "-1 -1" << endl;
  }
  else
  {
   cout << check_full << " " << full_map << endl;
  }
 }
 return 0;
Leave a Comment