Submission #1282413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282413		vectorlmn	Dangerous Skating (JOI16_skating)	C++20	100 / 100	452 ms	154588 KiB

skating

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
void ioopti(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}
void io(){
	freopen("skate.in","r",stdin);
	freopen("skate.out","w",stdout);
}
const int maxn=1e3+5;
int n,m;
char s[maxn][maxn];
int r1,c1,r2,c2;
vector<pair<pii,int> > g[maxn][maxn];
int r_lstblk[maxn][maxn],r_nxtblk[maxn][maxn],c_lstblk[maxn][maxn],c_nxtblk[maxn][maxn];
bitset<maxn> vis[maxn];
int dis[maxn][maxn];
void dij(){
	memset(dis,0x3f,sizeof dis);
	priority_queue<pair<int,pii>,vector<pair<int,pii> >,greater<pair<int,pii> > > q;
	q.push(mkpr(0,mkpr(r1,c1)));
	dis[r1][c1]=0;
	while(!q.empty()){
		auto cur=q.top().se;
		q.pop();
		int x=cur.fi,y=cur.se;
		if(vis[x][y])continue;
		vis[x][y]=1;
		for(auto& v:g[x][y]){
			int fx=v.fi.fi,fy=v.fi.se,w=v.se;
			if(dis[fx][fy]>dis[x][y]+w){
				dis[fx][fy]=dis[x][y]+w;
				q.push(mkpr(dis[fx][fy],mkpr(fx,fy)));
			}
		}
	}
	if(dis[r2][c2]>1e8){
		puts("-1");
		return;
	}
	printf("%d\n",dis[r2][c2]);
}
void solve(int id_of_test){
	scanf("%d%d",&n,&m);
	FOR(i,1,n){
		scanf("%s",s[i]+1);
	}
	read(r1);
	read(c1);
	read(r2);
	read(c2);
	FOR(i,1,n){
		int lst=1;
		FOR(j,1,m){
			if(s[i][j]=='#')lst=j;
			else r_lstblk[i][j]=lst;
		}
		lst=m;
		REP(j,m,1){
			if(s[i][j]=='#')lst=j;
			else r_nxtblk[i][j]=lst;
		}
	}
	FOR(j,1,m){
		int lst=1;
		FOR(i,1,n){
			if(s[i][j]=='#')lst=i;
			else c_lstblk[i][j]=lst;
		}
		lst=n;
		REP(i,n,1){
			if(s[i][j]=='#')lst=i;
			else c_nxtblk[i][j]=lst;
		}
	}
	
	FOR(i,1,n){
		FOR(j,1,m){
			if(s[i][j]=='#')continue;
			if(s[i][j-1]!='#'){
				g[i][j].eb(mkpr(mkpr(i,j-1),2));
			}
			if(s[i][j+1]!='#'){
				g[i][j].eb(mkpr(mkpr(i,j+1),2));
			}
			if(s[i-1][j]!='#'){
				g[i][j].eb(mkpr(mkpr(i-1,j),2));
			}
			if(s[i+1][j]!='#'){
				g[i][j].eb(mkpr(mkpr(i+1,j),2));
			}
		}
	}
	FOR(i,1,n){
		FOR(j,1,m){
			if(s[i][j]=='#')continue;
			{
				int lst=c_lstblk[i][j]+1;
				g[i][j].eb(mkpr(mkpr(lst,j),1));
			}
			{
				int nxt=c_nxtblk[i][j]-1;
				g[i][j].eb(mkpr(mkpr(nxt,j),1));
			}
			{
				int lst=r_lstblk[i][j]+1;
				g[i][j].eb(mkpr(mkpr(i,lst),1));
			}
			{
				int nxt=r_nxtblk[i][j]-1;
				g[i][j].eb(mkpr(mkpr(i,nxt),1));
			}
		}
	}
	dij();
}
int main()
{
	int T;
	T=1;
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}
/*
1. 对题意的理解能否和样例对的上？
2. 每一步操作，能否和自己的想法匹配？
3. 每一步操作的正确性是否有保证？
4. 是否考虑到了所有的 case？特别是极限数据。
5. 变量的数据类型是否与其值域匹配？
6. 时间复杂度有保证吗？
7. 空间多少 MB？
*/

Compilation message (stderr)

skating.cpp: In function 'void io()':
skating.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         freopen("skate.in","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
skating.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         freopen("skate.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skating.cpp: In function 'void solve(int)':
skating.cpp:112:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         scanf("%d%d",&n,&m);
      |         ~~~~~^~~~~~~~~~~~~~
skating.cpp:114:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |                 scanf("%s",s[i]+1);
      |                 ~~~~~^~~~~~~~~~~~~

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