BOJ 2645

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 51
#define INF 987654321

bool map[MAXN][MAXN];

struct node{
    int x;
    int y;
    int w;
    bool operator < (const node& a) const{
        return a.w < w;
    }
};
int dist[MAXN][MAXN];
pair<int,int> path[MAXN][MAXN];
priority_queue<node> pq;
int N,M,K;
int sx1,sy1,sx2,sy2;
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
// (x1,y1) -> (x2,y2)로 가기 위한 방향 체크
int find_dir(int x1, int y1, int x2, int y2){
    if (x2 - x1 > 0 ) return 1;
    else if (x2 - x1 < 0) return 3;
    else if (y2 - y1 > 0) return 0;
    return 2;
}

void bfs(){
    pq.push({sx1,sy1,0});
    dist[sx1][sy1] = 0;
    while (!pq.empty()){
        int x = pq.top().x;
        int y = pq.top().y;
        int cur_w = pq.top().w;
        pq.pop();
        if (dist[x][y] != cur_w) continue;
        for (int k =0 ;k<4; k++){
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx <= 0|| ny<=0 || nx> N || ny > N) continue;
            int next_w;
            if (map[nx][ny]) next_w = cur_w+K;
            else next_w = cur_w+1;
            if (dist[nx][ny] > next_w){
                dist[nx][ny] = next_w;
                path[nx][ny] = {x,y};
                pq.push({nx,ny,next_w});
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    for (int i = 1; i <= N; i++){
        for (int j = 1; j<=N; j++){
            dist[i][j] = INF;
        }
    }
    cin >> sx1 >> sy1 >> sx2 >> sy2;
    cin >> K >> M;
    int x,y;
    while (M--){
        int num;
        cin >> num >> x >> y;
        for (int i = 0; i< num-1; i++){
            int nx,ny;
            cin >> nx >> ny;
            int d = find_dir(x,y,nx,ny);
            while (x != nx || y != ny){
                map[x][y] = true;
                x += dx[d];
                y += dy[d];
            }
            map[x][y] = true;
        }
    }
    bfs();
    cout << dist[sx2][sy2]+1 <<"\n";
    vector<pair<int,int> > trace;
    trace.push_back({sx2,sy2});
    pair<int,int> tmp = path[sx2][sy2];
    int dir = find_dir(sx2,sy2,tmp.first,tmp.second);
    sx2 = tmp.first;
    sy2 = tmp.second;
    while (sx2 != sx1 || sy2 != sy1){
        pair<int,int> tmp = path[sx2][sy2];
        int tmp_dir = find_dir(sx2,sy2,tmp.first,tmp.second);
        if (dir != tmp_dir){
            dir = tmp_dir;
            trace.push_back({sx2,sy2});
        }
        sx2 = tmp.first;
        sy2 = tmp.second;
    }
    trace.push_back({sx1,sy1});
    reverse(trace.begin(),trace.end());
    cout << trace.size() <<" ";
    for (int i = 0 ; i < trace.size(); i++){
        cout << trace[i].first <<" " <<trace[i].second <<" ";
    }
    return 0;
}