fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. string s;int a[7][7];
  5.  
  6. bool isWallPartitioned(int x,int y){
  7. 		if(x==0&&y>0&&y<6&&a[1][y]==1&&a[0][y+1]==0&&a[0][y-1]==0)return true;
  8.         if(x==6&&y>0&&y<6&&a[5][y]==1&&a[6][y+1]==0&&a[6][y-1]==0)return true;
  9.         if(y==0&&x>0&&x<6&&a[x][1]==1&&a[x+1][0]==0&&a[x-1][0]==0)return true;
  10.         if(y==6&&x>0&&x<6&&a[x][5]==1&&a[x+1][6]==0&&a[x-1][6]==0)return true;
  11.         else return false;
  12. }
  13. bool isLooped(int x,int y){
  14. 	if(x==0||x==6||y==0||y==6)return false;
  15. 	if(a[x][y+1]==1&&a[x][y-1]==1&&a[x-1][y]==0&&a[x+1][y]==0)return true;
  16. 	if(a[x+1][y]==1&&a[x-1][y]==1&&a[x][y+1]==0&&a[x][y-1]==0)return true;
  17. 	return false;
  18. }
  19.  
  20.  
  21. int solve(int x,int y,int i){
  22.  
  23. 	if(x==6&&y==0){
  24. 		if(i==48)return 1;
  25. 		return 0;
  26. 	}
  27. 	if(i==48){
  28. 		return 0;
  29. 	}
  30. 	if(isWallPartitioned(x,y))return 0;
  31. 	if(isLooped(x,y))return 0;
  32. 	if(s[i]=='?'){
  33. 		int r[]={0,1,0,-1};
  34. 		int c[]={-1,0,1,0};
  35. 		int k=0;
  36. 		for(int j=0;j<4;j++){
  37. 			int xx= x+r[j];
  38. 			int yy= y+c[j];
  39. 			if(xx<0||xx>6)continue;
  40. 			if(yy<0||yy>6)continue;
  41. 			if(a[xx][yy]==1)continue;
  42. 			a[xx][yy]=1;
  43. 			k+=solve(xx,yy,i+1);
  44. 			a[xx][yy]=0;
  45. 		}
  46. 		return k;
  47. 	}
  48.  
  49. 	if(s[i]=='L')y--;
  50. 	else if(s[i]=='R')y++;
  51. 	else if(s[i]=='D')x++;
  52. 	else if(s[i]=='U')x--;
  53. 	if(x<0||x>6)return 0;
  54. 	if(y<0||y>6)return 0;
  55. 	if(a[x][y]==1)return 0;
  56. 	a[x][y]=1;
  57. 	int k=solve(x,y,i+1);
  58. 	a[x][y]=0;
  59. 	return k;
  60.  
  61. }
  62.  
  63. int main() {
  64. 	ios_base::sync_with_stdio(false);
  65.     cin.tie(NULL);
  66. 	a[0][0]=1;
  67. 	cin>>s;
  68. 	cout<<solve(0,0,0);
  69. 	return 0;
  70. }
Success #stdin #stdout 0.93s 4952KB
comments (?)
stdin
copy 
???????????????????????????????????????????????D
stdout
copy 
45647
https://ideone.com/r9lZ5z
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!