제출 #256249

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
256249		shayan_p	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1179 ms	107400 KiB

tracks

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 4010, mod = 1e9 + 7, inf = 1e9 + 10;

int n, m;
string s[maxn];
int a[maxn][maxn];
bool mark[maxn][maxn];

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
    
    cin >> n >> m;
    for(int i = 0; i < n; i++){
	cin >> s[i];	
    }
    assert(s[0][0] == s[n-1][m-1] && s[0][0] != '.');
    char c = s[0][0];
    for(int i = 0; i < n; i++){
	for(int j = 0; j < m; j++){
	    a[i][j] = (s[i][j] == '.' ? -1 : (s[i][j] != c));
	}
    }
    queue<pii> q[2];
    q[0].push({0,0});
    mark[0][0] = 1;
    int ans = 0;
    while(sz(q[ans & 1])){
	while(sz(q[ans & 1])){
	    pii p = q[ans & 1].front();
	    q[ans & 1].pop();
	    for(int i = 0; i < 4; i++){
		int x = p.F + dx[i], y = p.S + dy[i];
		if(x >= 0 && y >= 0 && x < n && y < m && a[x][y] != -1 && mark[x][y] == 0)
		    mark[x][y] = 1, q[a[x][y]].push({x, y});
	    }
	}
	ans++;
    }
    return cout << ans << endl, 0;
}

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