Submission #519674

#	Time	Username	Problem	Language	Result	Execution time	Memory
519674		zhangjishen	Tracks in the Snow (BOI13_tracks)	C++98	100 / 100	1297 ms	103420 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
template<typename T> bool chkmin(T &a, T b){return b < a ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return b > a ? a = b, 1 : 0;}
const int MAXN = 4e3 + 10, inf = INT_MAX;
const int mv[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int n, m;
char g[MAXN][MAXN];

bool valid(int x, int y){
	return x >= 0 && x < n && y >= 0 && y < m && g[x][y] != '.';
}

inline int id(int x, int y){ return x * m + y; }
inline int x(int id){ return id / m; }
inline int y(int id){ return id % m; }

deque<int> q;
int d[MAXN * MAXN];
int bfs(){
	for(int i = 0; i < n * m; i++)
		d[i] = inf;
	d[0] = 1; q.pb(0);
	int ans = 0;
	while(!q.empty()){
		int u = q.front(); q.pop_front();
		chkmax(ans, d[u]);
		for(int k = 0; k < 4; k++){	// implicit edges
			int nx = x(u) + mv[k][0];
			int ny = y(u) + mv[k][1];
			int v = id(nx, ny);
			if(valid(nx, ny) && d[v] == inf){
				if(g[x(u)][y(u)] == g[nx][ny]){	// 0
					d[v] = d[u];
					q.pf(v);
				}else{
					d[v] = d[u] + 1;
					q.pb(v);
				}
			}
		}
	}
	return ans;
}

int main(){
	// input
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			scanf(" %c", &g[i][j]);
	// 0/1 bfs
	int track = bfs();
	printf("%d\n", track);
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
tracks.cpp:54:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |    scanf(" %c", &g[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~

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