제출 #1015784

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1015784		KALARRY	Tracks in the Snow (BOI13_tracks)	C++14	82.50 / 100	2021 ms	1048576 KiB

tracks

//chockolateman

#include<bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int H,W,di[4] = {1,-1,0,0},dj[4] = {0,0,1,-1},dist[20000005];
char grid[4005][4005];
vector<pair<int,int>> adj[20000005];

int id(int i,int j)
{
    return (i-1)*W + j;
}

bool is_ok(int i,int j)
{
    if(i >= 1 && i <= H && j >= 1 && j <= W && grid[i][j] != '.')
        return true;
    return false;
}

void connect_neighs()
{
    for(int i = 1 ; i <= H ; i++)
        for(int j = 1 ; j <= W ; j++)
        {
            if(grid[i][j]=='.')
                continue;
            for(int k = 0 ; k <= 3 ; k++)
            {
                int new_i = i + di[k];
                int new_j = j + dj[k];
                if(is_ok(new_i,new_j))
                {
                    if(grid[i][j]==grid[new_i][new_j])
                        adj[id(i,j)].push_back({id(new_i,new_j),0});
                    else
                        adj[id(i,j)].push_back({id(new_i,new_j),1});
                }
            }
        }
}

void BFS(int start)
{
    for(int i = 1 ; i <= H ; i++)
        for(int j = 1 ; j <= W ; j++)
            if(grid[i][j]!='.')
                dist[id(i,j)] = INF;
    deque<int> q;
    dist[start] = 0;
    if(grid[1][1]!='.')
        dist[start] = 1;
    q.push_back(start);
    while(!q.empty())
    {
        int v = q.front();
        q.pop_front();
        for(auto e : adj[v])
        {
            int u = e.first;
            int w = e.second;
            if(dist[v] + w < dist[u])
            {
                dist[u] = dist[v] + w;
                if(w==0)
                    q.push_front(u);
                else
                    q.push_back(u);
            }
        }
    }
}

int main()
{
    scanf("%d%d",&H,&W);
    for(int i = 1 ; i <= H ; i++)
        for(int j = 1 ; j <= W ; j++)
            scanf(" %c",&grid[i][j]);
    connect_neighs();
    BFS(id(1,1));
    int ans = 0;
    for(int i = 1 ; i <= H ; i++)
        for(int j = 1 ; j <= W ; j++)
            ans = max(ans,dist[(id(i,j))]);
    printf("%d\n",ans);
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

tracks.cpp: In function 'int main()':
tracks.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |     scanf("%d%d",&H,&W);
      |     ~~~~~^~~~~~~~~~~~~~
tracks.cpp:83:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |             scanf(" %c",&grid[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 52.5 / 70