글 읽기 - 6%에서 틀리네요. 반례 좀 찾아주세요ㅠㅠ

junelee0997 3년 전 0

계속 6%에서 틀립니다. 반례 좀 찾아주세요ㅠㅠ

#include <iostream>
#include <queue>
using namespace std;
int n, v[510][510][3], map[510][510][3], num = 0, dx[] = { 0, 1, 0, -1, -1, 1}, dy[] = {1, 0, -1, 0, -1, -1}, dx2[] = { 0, -1, 1, -1, 0, 1}, dy2[] = {1, 1, 1, 0, -1, 0}, res[250010];
queue <pair<int, int>> stat;
int main() {
  cin >> n;
  for(int i = 1; i <= n; i++)
  {
    if(i % 2 == 1)
    {
      for(int j = 1; j <= n; j++)
      {
        cin >> map[i][j][0] >> map[i][j][1];
        map[i][j][2] = ++num;
      }
    }
    else{
      for(int j = 1; j <= n - 1; j++)
      {
        cin >> map[i][j][0] >> map[i][j][1];
        map[i][j][2] = ++num;
      }
    }
  }
  stat.push(make_pair(1, 1));
  v[1][1][2] = 1;
  v[1][1][0] = 1;
  v[1][1][1] = 1;
  while(!stat.empty())
  {
    int st = stat.front().first, st2 = stat.front().second;
    stat.pop();
    if(st % 2 == 1)
    {
      for(int i = 0; i < 3; i++)
      {
        int nx = st + dx[i], ny = st2 + dy[i];
        if(map[nx][ny][0] == 0) continue;
        if(map[nx][ny][0] == map[st][st2][1] && v[nx][ny][2] == 0)
        {
          stat.push(make_pair(nx, ny));
          v[nx][ny][0] = st;
          v[nx][ny][1] = st2;
          v[nx][ny][2] = map[nx][ny][2];
        }
      }
      for(int i = 3; i < 6; i++)
      {
        int nx = st + dx[i], ny = st2 + dy[i];
        if(map[nx][ny][0] == 0) continue;
        if(map[nx][ny][1] == map[st][st2][0] && v[nx][ny][2] == 0)
        {
          stat.push(make_pair(nx, ny));
          v[nx][ny][0] = st;
          v[nx][ny][1] = st2;
          v[nx][ny][2] = map[nx][ny][2];
        }
      }
    }
    if(st % 2 == 0)
    {
      for(int i = 0; i < 3; i++)
      {
        int nx = st + dx2[i], ny = st2 + dy2[i];
        if(map[nx][ny][0] == 0) continue;
        if(map[nx][ny][0] == map[st][st2][1] && v[nx][ny][2] == 0)
        {
          stat.push(make_pair(nx, ny));
          v[nx][ny][0] = st;
          v[nx][ny][1] = st2;
          v[nx][ny][2] = map[nx][ny][2];
        }
      }
      for(int i = 3; i < 6; i++)
      {
        int nx = st + dx2[i], ny = st2 + dy2[i];
        if(map[nx][ny][0] == 0) continue;
        if(map[nx][ny][1] == map[st][st2][0] && v[nx][ny][2] == 0)
        {
          stat.push(make_pair(nx, ny));
          v[nx][ny][0] = st;
          v[nx][ny][1] = st2;
          v[nx][ny][2] = map[nx][ny][2];
        }
      }
    }
  }
  int c = 0;
  int f, f2;
  for(int i = n; i >= 1; i--)
  {
    for(int j = n; j >= 1; j--)
    {
      if(v[i][j][2] != 0)
      {
        f=i,f2=j;
        c = 1;
        break;
      }
    }
    if(c) break;
  }
  int si = 0;
  while(f != 1 || f2 != 1)
  {
    res[++si] = map[f][f2][2];
    int nf = v[f][f2][0];
    f2 = v[f][f2][1];
    f = nf;
  }
  cout << si + 1 << '\n';
  cout << "1 ";
  for(int i = si; i >= 1; i--)
  {
    cout << res[i] << " ";
  }
}

nickytv 2년 전 0

갈아엎으십쇼

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

6%에서 틀리네요. 반례 좀 찾아주세요ㅠㅠ

junelee0997 3년 전 0

nickytv 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말