Submission #28622

#	Time	Username	Problem	Language	Result	Execution time	Memory
28622		점수판에 아이디와 팀명이 같이 표기되니, 신중하게 적어주세요. (#68)	On the Grid (FXCUP2_grid)	C++14	0 / 1	0 ms	2412 KiB

grid

#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi; typedef pair<ll, int> pli; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 3e2 + 10;

int N, M, Nr[MAX_N * MAX_N];
map<pi, int> dis;
set<pi> inQ;
pi toPi(int s, int t) {
	if(t == 0) return pi(s/M, s%M);
	return pi(s/N, s%N);
}
int toS(int x, int y, int t) {
	if(t == 0) return x*M + y;
	return x*N + y;
}
bool isIn(int x, int y, int t) {
	if(t == 0) return !(x<0 || y<0 || x>=N || y>=M);
	return !(x<0 || y<0 || x>=M || y>=N);
}
queue<pi> Q;
void push(int x, int y, int c) {
//	printf("push %d %d | %d\n", x, y, c);
	if(dis[pi(x,y)] == 0 || dis[pi(x,y)] > c) {
		dis[pi(x,y)] = c;
		if(inQ.find(pi(x, y)) == inQ.end()) {
			inQ.insert(pi(x, y));
			Q.push(pi(x, y));
		}
	}
}
void findAns(int a, int b) {
	if(a == 0 && b == 0) {
		Nr[0] = -1;
		return;
	}
	int ax, ay; tie(ax, ay) = toPi(a, 0);
	int bx, by; tie(bx, by) = toPi(b, 1);
	vector<int> ls[2];
	for(int k=0; k<4; k++) {
		int nx = ax + "1012"[k] - '1', ny = ay + "0121"[k] - '1';
		if(!isIn(nx, ny, 0)) continue;
		int na = toS(nx, ny, 0);
		ls[0].push_back(na);
		if(dis[pi(na, b)] + Nr[a] == dis[pi(a, b)]) {
			Nr[a] = -1;
			return findAns(na, b);
		}
	}
	for(int k=0; k<4; k++) {
		int nx = bx + "1012"[k] - '1', ny = by + "0121"[k] - '1';
		if(!isIn(nx, ny, 1)) continue;
		int nb = toS(nx, ny, 1);
		ls[1].push_back(nb);
		if(dis[pi(a, nb)] + Nr[b] == dis[pi(a, b)]) {
			Nr[b] = -1;
			return findAns(a, nb);
		}
	}
	if(a == b) {
		for(int na : ls[0]) for(int nb : ls[1]) {
			if(dis[pi(na, nb)] + Nr[a] == dis[pi(a, b)]) {
				Nr[a] = -1;
				return findAns(na, nb);
			}
		}
	}
	assert(false);
}
int main() {
	cin >> M >> N;
	for(int i=0; i<N*M; i++) scanf("%d", &Nr[i]);
	Q.push(pi(0, 0)); dis[pi(0, 0)] = Nr[0]; inQ.insert(pi(0, 0));
	while(!Q.empty()) {
		inQ.erase(inQ.find(Q.front()));
		int a, b; tie(a, b) = Q.front(); Q.pop();
//		if(a == b) printf("%d %d [%d]\n", a, b, dis[pi(a, b)]);
		if(a+1 == N*M && b+1 == N*M) {
			printf("%d\n", dis[pi(a, b)]);
			break;
		}
		int ax, ay; tie(ax, ay) = toPi(a, 0);
		int bx, by; tie(bx, by) = toPi(b, 1);
		vector<int> ls[2];
		for(int k=0; k<4; k++) {
			int nx = ax + "1012"[k] - '1', ny = ay + "0121"[k] - '1';
			if(!isIn(nx, ny, 0)) continue;
			int na = toS(nx, ny, 0);
			ls[0].push_back(na);
			push(na, b, dis[pi(a,b)] + Nr[na]);
		}
		for(int k=0; k<4; k++) {
			int nx = bx + "1012"[k] - '1', ny = by + "0121"[k] - '1';
			if(!isIn(nx, ny, 1)) continue;
			int nb = toS(nx, ny, 1);
			ls[1].push_back(nb);
			push(a, nb, dis[pi(a, b)] + Nr[nb]);
		}
		for(int k=0; k<2; k++) {
			sort(ALL(ls[k]));
		}
		for(int i=0, j=0; i<SZ(ls[0]) && j<SZ(ls[1]); ) {
			if(ls[0][i] == ls[1][j]) {
				int v = ls[0][i];
//				printf("when %d %d -> %d %d\n", a, b, v, v);
				push(v, v, dis[pi(a, b)] + Nr[v]);
				i++;
			}else if(ls[0][i] < ls[1][j]) i++; else j++;
		}
	}
	findAns(N*M-1, N*M-1);
	for(int i=0; i<N; i++, puts("")) for(int j=0; j<M; j++) {
		printf("%d ", Nr[i*M+j] == -1 ? 1 : 0);
	}
	return 0;
}

Compilation message (stderr)

grid.cpp: In function 'int main()':
grid.cpp:84:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N*M; i++) scanf("%d", &Nr[i]);
                                              ^

• Subtask 1: 0 / 1