Submission #328822

#	Time	Username	Problem	Language	Result	Execution time	Memory
328822		egas	Nautilus (BOI19_nautilus)	C++14	66 / 100	418 ms	262144 KiB

nautilus

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


int dp[101][101][5001];
int solve(int r,int c,int idx,vector<string> &a,string &b){
	//Invalid Cells
	if(r<0 or r>=a.size() or c<0 or c>=a[0].size())return 0;
	
	//Cell is land
	if(a[r][c]!='.')return 0;
	
	// Reached End
	if(idx==b.size()){		
		if(dp[r][c][idx]!=-1) return 0;		
		dp[r][c][idx]=1;	
		return 1;
	}
	
	// Already Visited
	if(dp[r][c][idx]!=-1) return 0;
	
	if(b[idx]=='?'){
		dp[r][c][idx] = solve(r,c-1,idx+1,a,b)
					 + solve(r,c+1,idx+1,a,b)
					 + solve(r-1,c,idx+1,a,b)
					 + solve(r+1,c,idx+1,a,b);
		return dp[r][c][idx];
		
	}else{
		int ans=0;
		if(b[idx]=='W')
			ans= solve(r,c-1,idx+1,a,b);
		else if(b[idx]=='E')
			ans = solve(r,c+1,idx+1,a,b);
		else if(b[idx]=='N')
			ans = solve(r-1,c,idx+1,a,b);
		else if(b[idx]=='S')
			ans = solve(r+1,c,idx+1,a,b);
		dp[r][c][idx]=ans;
		return dp[r][c][idx];
	}
	return 0;
}



int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
	int r,c,m;
	cin >> r >> c >> m;
	vector<string> a;
	for(int i=0;i<r;i++){
		string temp;cin >> temp;
		a.push_back(temp);
	}
	
	string b;
	cin >> b;
	memset(dp,-1,sizeof dp);
	int res=0;
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			res+=solve(i,j,0,a,b);
		}
	}	
	cout << res << endl;
    return 0;
}

Compilation message (stderr)

nautilus.cpp: In function 'int solve(int, int, int, std::vector<std::__cxx11::basic_string<char> >&, std::string&)':
nautilus.cpp:8:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |  if(r<0 or r>=a.size() or c<0 or c>=a[0].size())return 0;
      |            ~^~~~~~~~~~
nautilus.cpp:8:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |  if(r<0 or r>=a.size() or c<0 or c>=a[0].size())return 0;
      |                                  ~^~~~~~~~~~~~~
nautilus.cpp:14:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  if(idx==b.size()){
      |     ~~~^~~~~~~~~~

• Subtask 1: 29 / 29
• Subtask 2: 37 / 37
• Subtask 3: 0 / 34