Submission #696505

#	Time	Username	Problem	Language	Result	Execution time	Memory
696505		rainboy	Sandwich (JOI16_sandwich)	C11	100 / 100	1331 ms	14864 KiB

sandwich

/* https://www.ioi-jp.org/camp/2016/2016-sp-tasks/2016-sp-d2-sandwich-review.pdf */
#include <stdio.h>
#include <string.h>

#define N	400
#define M	400
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }

char cc[N][M + 1], visited[N][M], tt[N][M]; int n, m, cnt;

int dfs(int i, int j, int t) {
	if (visited[i][j])
		return visited[i][j] == 2 || tt[i][j] != t;
	visited[i][j] = 2, tt[i][j] = t, cnt++;
	if (t == 0) {
		if (j + 1 < m && dfs(i, j + 1, 0))
			return 1;
		if (cc[i][j] == 'N' && i > 0 && dfs(i - 1, j, cc[i - 1][j] == 'N' ? 0 : 1))
			return 1;
		if (cc[i][j] == 'Z' && i + 1 < n && dfs(i + 1, j, cc[i + 1][j] == 'Z' ? 0 : 1))
			return 1;
	} else {
		if (j > 0 && dfs(i, j - 1, 1))
			return 1;
		if (cc[i][j] == 'Z' && i > 0 && dfs(i - 1, j, cc[i - 1][j] == 'N' ? 0 : 1))
			return 1;
		if (cc[i][j] == 'N' && i + 1 < n && dfs(i + 1, j, cc[i + 1][j] == 'Z' ? 0 : 1))
			return 1;
	}
	visited[i][j] = 1;
	return 0;
}

int main() {
	static int ans[N][M];
	int i, i_, j, j1, j2, r, tmp;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	for (i = 0; i < n; i++)
		memset(ans[i], 0x3f, m * sizeof *ans[i]);
	for (r = 0; r < 2; r++) {
		for (i = 0; i < n; i++) {
			for (i_ = 0; i_ < n; i_++)
				memset(visited[i_], 0, m * sizeof *visited[i_]);
			cnt = 0;
			for (j = 0; j < m; j++) {
				if (dfs(i, j, 1))
					break;
				ans[i][j] = min(ans[i][j], cnt * 2);
			}
		}
		for (i = 0; i < n; i++) {
			for (j1 = 0, j2 = m - 1; j1 < j2; j1++, j2--) {
				tmp = cc[i][j1], cc[i][j1] = cc[i][j2], cc[i][j2] = tmp;
				tmp = ans[i][j1], ans[i][j1] = ans[i][j2], ans[i][j2] = tmp;
			}
			for (j = 0; j < m; j++)
				cc[i][j] = cc[i][j] == 'N' ? 'Z' : 'N';
		}
	}
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			printf("%d%c", ans[i][j] == INF ? -1 : ans[i][j], j + 1 < m ? ' ' : '\n');
	return 0;
}

Compilation message (stderr)

sandwich.c: In function 'main':
sandwich.c:40:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
sandwich.c:42:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~

• Subtask 1: 35 / 35
• Subtask 2: 65 / 65