Submission #97132

#	Time	Username	Problem	Language	Result	Execution time	Memory
97132		maruii	Dangerous Skating (JOI16_skating)	C++17	13 / 100	1081 ms	263168 KiB

skating

#include <bits/stdc++.h>
using namespace std;
int R, C, dx[] = {1,0,-1,0}, dy[] = {0,1,0,-1};
char A[1005][1005];
using pii = pair<int, int>;
struct Node{
	int x,y,dist;
	vector<pii> vec;
};
queue<Node> q;
int main(){
	scanf("%d%d",&R,&C);
	for(int i=0; i<R; ++i)
		scanf("%s",A[i]);
	Node st;
	for(int i=0; i<R; ++i) for(int j=0; j<C; ++j) if(A[i][j]=='#') st.vec.push_back({i, j});
	st.dist = 0;
	int ex, ey;
	scanf("%d%d",&st.x,&st.y), --st.x, --st.y;
	scanf("%d%d",&ex,&ey), --ex, --ey;
	sort(st.vec.begin(), st.vec.end());
	q.push(st);
	while(q.size()){
		auto cur = q.front(); q.pop();
		if(cur.x == ex && cur.y == ey) return !printf("%d",cur.dist);
		for(int i=0; i<4; ++i){
			int j;
			for(j=0; j<1000; ++j){
				int nx = cur.x+dx[i]*j, ny = cur.y+dy[i]*j;
				if(nx<0 || ny<0 || nx>=R || ny>=C || *lower_bound(cur.vec.begin(), cur.vec.end(), pii(nx, ny))==pii(nx, ny)) break;
			}
			if(j==0) break;
			if(j>1){
				--j;
				auto t = cur;
				t.x += dx[i]*j, t.y += dy[i]*j, ++t.dist;
				int ub = upper_bound(t.vec.begin(), t.vec.end(), pii(cur.x, cur.y))-t.vec.begin();
				t.vec.push_back({0, 0});
				for(int i=t.vec.size()-1; i>ub; --i) t.vec[i] = t.vec[i-1];
				t.vec[ub] = {cur.x, cur.y};
				q.push(t);
			}
		}
	}
	printf("-1");
	return 0;
}

Compilation message (stderr)

skating.cpp: In function 'int main()':
skating.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&R,&C);
  ~~~~~^~~~~~~~~~~~~~
skating.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",A[i]);
   ~~~~~^~~~~~~~~~~
skating.cpp:19:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&st.x,&st.y), --st.x, --st.y;
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
skating.cpp:20:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&ex,&ey), --ex, --ey;
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 0 / 65
• Subtask 3: 0 / 22