Submission #77309

#	Time	Username	Problem	Language	Result	Execution time	Memory
77309		ekrem	Robots (APIO13_robots)	C++98	0 / 100	100 ms	118216 KiB

robots

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define inf 1000000007
#define N 505
using namespace std;

typedef pair < int , int > ii;

int n, m, k, a[N][N], d[10][N][N], u[10][N][N], dp[10][10][N][N];
ii git[4][N][N];
int o[] = {-1, 0, 1, 0};
int p[] = {0, 1, 0, -1};
char x;

inline bool bak(int i, int j){return !(i > n or j > m or i < 1 or j < 1 or a[i][j] == -1);}

ii gt(int i, int j, int yon){
	ii &r = git[yon][i][j];
	if(r.st != -1)
		return r;
	r = mp(inf, inf);
	if(!bak(i + o[yon], j + p[yon]))
		return r = mp(i, j);
	if(a[i][j] == -2)
		return r = gt(i + o[(yon + 1)%4], j + p[(yon + 1)%4], (yon + 1)%4);
	if(a[i][j] == -3)
		return r = gt(i + o[(yon + 3)%4], j + p[(yon + 3)%4], (yon + 3)%4);
	return r = gt(i + o[yon], j + p[yon], yon);
}

void bul(int k){
	int x, y;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			if(a[i][j] == k){
				x = i;
				y = j;
				break;
			}
	priority_queue < pair < int , ii > > b;
	d[k][x][y] = 0;
	b.push(mp(0, mp(x, y)));
	while(!b.empty()){
		int yol = -b.top().st;
		int x = b.top().nd.st;
		int y = b.top().nd.nd;
		b.pop();
		u[k][x][y] = 1;
		for(int z = 0; z < 4; z++){
			ii g = gt(x, y, z);
			d[k][g.st][g.nd] = min(d[k][g.st][g.nd], yol + 1);
			if(!u[k][g.st][g.nd])
				b.push(mp(-d[k][g.st][g.nd], mp(g.st, g.nd)));
		}
	}
}

int f(int a, int b, int x, int y){
	int &r = dp[a][b][x][y];
	if(r != -1)
		return r;
	r = inf;
	if(a > b)
		return r = 0;
	if(a == b)
		return r = d[a][x][y];
	for(int i = a; i < b; i++)
		r = min(r, f(a, i, x, y) + f(i + 1, b, x, y));
	return 0;
}

int main() {
	freopen("in.txt", "r", stdin);
	freopen("outt.txt", "w", stdout);
	memset(git, -1, sizeof git);
	memset(dp, -1, sizeof dp);
	memset(d, 20, sizeof d);
	scanf("%d %d %d",&k ,&m ,&n);
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++){
			scanf(" %c",&x);
			if(x == 'x')
				a[i][j] = -1;
			else if(x == '.')
				a[i][j] = 0;
			else if(x == 'C')
				a[i][j] = -2;
			else if(x == 'A')
				a[i][j] = -3;
			else
				a[i][j] = x - '0';
		}
	for(int i = 1; i <= k; i++)
		bul(i);
	// cout << d[1][3][1] << endl;
	return 0;
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:76:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("in.txt", "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:77:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("outt.txt", "w", stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:81: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:84:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c",&x);
    ~~~~~^~~~~~~~~~
robots.cpp: In function 'void bul(int)':
robots.cpp:45:11: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  b.push(mp(0, mp(x, y)));
           ^
robots.cpp:45:11: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40