Submission #258107

#	Time	Username	Problem	Language	Result	Execution time	Memory
258107		sjimed	Sandwich (JOI16_sandwich)	C++14	100 / 100	5237 ms	10772 KiB

sandwich

#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(NULL)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define all(v) (v).begin(), (v).end()
#define pre(a) cout<<fixed; cout.precision(a)

#define mp make_pair

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;

int n, m;
string s[444];
int chk[444][444];
int ans[444][444];

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int t[2][2][2] = {
	1, 2,
	0, 3,
	2, 3,
	0, 1
};

int dir[2][4] = {
	1, 0, 0, 1,
	1, 1, 0, 0
};

int dfs(int x, int y, int d) {
	if(chk[x][y] == 1) return inf;
	if(chk[x][y] == 2) return 0;

	//cout << x << "!!! " << y << " " << d << endl;

	chk[x][y]=1;

	int ret = 2;

	for(int i=0; i<2; i++) {
		int nx = x + dx[t[s[x][y]][d][i]];
		int ny = y + dy[t[s[x][y]][d][i]];

		if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

		ret += dfs(nx, ny, dir[s[nx][ny]][t[s[x][y]][d][i]]);

		ret = min(inf, ret);
	}

	chk[x][y]=2;

	return ret;
}

int main() {
	fast;

	cin >> n >> m;

	for(int i=0; i<n; i++) {
		cin >> s[i];

		for(int j=0; j<m; j++) {
			if(s[i][j] == 'N') s[i][j] = 0;
			else s[i][j] = 1;

			ans[i][j] = inf;
		}
	}

	for(int j=0; j<m; j++) {

		memset(chk, 0, sizeof(chk));

		int sum = 0;
		
		for(int i=0; i<n; i++) {
			sum += dfs(i, j, 0);

			sum = min(sum, inf);

			ans[i][j] = min(ans[i][j], sum);
		}

		memset(chk, 0, sizeof(chk));

		sum = 0;
		
		for(int i=n-1; i>=0; i--) {
			sum += dfs(i, j, 1);

			sum = min(sum, inf);

			ans[i][j] = min(ans[i][j], sum);
		}		
	}

	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(ans[i][j] >= inf) cout << "-1 ";
			else cout << ans[i][j] << " ";
		}
		cout << "\n";
	}
}

Compilation message (stderr)

sandwich.cpp: In function 'int dfs(int, int, int)':
sandwich.cpp:52:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   int nx = x + dx[t[s[x][y]][d][i]];
                            ^
sandwich.cpp:53:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   int ny = y + dy[t[s[x][y]][d][i]];
                            ^
sandwich.cpp:57:35: warning: array subscript has type 'char' [-Wchar-subscripts]
   ret += dfs(nx, ny, dir[s[nx][ny]][t[s[x][y]][d][i]]);
                                   ^
sandwich.cpp:57:46: warning: array subscript has type 'char' [-Wchar-subscripts]
   ret += dfs(nx, ny, dir[s[nx][ny]][t[s[x][y]][d][i]]);
                                              ^

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