oj.uz

답안 #252108

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
252108 2020-07-24T08:27:58 Z T0p_ 로봇 (APIO13_robots) C++14
30 / 100
 91 ms 163844 KB 
#include<bits/stdc++.h>
using namespace std;

struct DJK
{
	int i;
	int j;
	int s;
	long long w;
	bool operator < (const DJK & o) const{
		return w > o.w;
	}
};

int n, m;
int di[4] = {-1, 0, 1, 0}, dj[4] = {0, 1, 0, -1};
long long dis[505][505][515];
pair<int, int> des[4][505][505];
char t[505][505];
queue<pair<int, int>> bfs;
priority_queue<DJK> djk;
bool visit[505][505][515];

pair<int, int> compute(int i, int j, int d)
{
	if(des[d][i][j].first) return des[d][i][j];
	int dd = d;
	if(t[i][j] == 'A')
	{
		dd += 3;
		dd %= 4;
	}
	else if(t[i][j] == 'C')
	{
		dd += 5;
		dd %= 4;
	}
	int ii = i + di[dd], jj = j + dj[dd];
	if(ii < 1 || jj < 1 || ii > n || jj > m || t[ii][jj] == 'x') return des[d][i][j] = {i, j};
	return des[d][i][j] = compute(ii, jj, dd);
}

int main()
{
	int K;
	scanf(" %d %d %d",&K,&m,&n);
	for(int i=1 ; i<=n ; i++)
		scanf(" %s",t[i]+1);
	for(int i=1 ; i<=n ; i++)
		for(int j=1 ; j<=m ; j++)
		{
			for(int k=1 ; k<(1<<K) ; k++) dis[i][j][k] = 1e9;
			if(t[i][j] == 'x') continue ;
			if('1' <= t[i][j] && t[i][j] <= '9')
			{
				int s = 1<<(t[i][j]-'0'-1);
				dis[i][j][s] = 0;
				djk.push({i, j, s, 0});
			}
			for(int k=0 ; k<4 ; k++)
				compute(i, j, k);
		}
	while(!djk.empty())
	{
		int i = djk.top().i;
		int j = djk.top().j;
		int s = djk.top().s;
		long long w = djk.top().w;
		djk.pop();
		if(visit[i][j][s]) continue ;
		visit[i][j][s] = true;
		if(s+1 == (1<<K))
		{
			printf("%d\n",w);
			return 0;
		}
		for(int k=0 ; k<4 ; k++)
		{
			int ii = des[k][i][j].first, jj = des[k][i][j].second;
			for(int it=0 ; it<(1<<K) ; it++)
			{
				int ss = it|s;
				if(dis[ii][jj][it] != 1e9 && dis[ii][jj][ss] > dis[ii][jj][it] + w + 1)
				{
					dis[ii][jj][ss] = dis[ii][jj][it] + w + 1;
					djk.push({ii, jj, ss, dis[ii][jj][ss]});
				}
			}
		}
	}
	printf("-1\n");
	return 0;
}

/*
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
*/

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:74:19: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
    printf("%d\n",w);
                   ^
robots.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %d %d %d",&K,&m,&n);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %s",t[i]+1);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 1024 KB Output is correct
5 Correct 1 ms 1024 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 1024 KB Output is correct
5 Correct 1 ms 1024 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 512 KB Output is correct
9 Correct 0 ms 512 KB Output is correct
10 Correct 1 ms 896 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 1024 KB Output is correct
5 Correct 1 ms 1024 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 512 KB Output is correct
9 Correct 0 ms 512 KB Output is correct
10 Correct 1 ms 896 KB Output is correct
11 Runtime error 91 ms 163844 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 1024 KB Output is correct
5 Correct 1 ms 1024 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 512 KB Output is correct
9 Correct 0 ms 512 KB Output is correct
10 Correct 1 ms 896 KB Output is correct
11 Runtime error 91 ms 163844 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -