ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 1577
    알고리즘/acmicpc 2015. 10. 16. 22:17

    아 도로문제 ㅠㅠ

    예전부터 이상하게 틀리던 문젠데 오늘 풀었는데 또 틀렸다. 대체 뭐가 문제인가 해서 친구한테 물어봤더니 장애물 저장방식에 문제가 있다고 했다...


    사실 이문제는 별로 어려운 문제는 아닌데말이다... 

    내 실수는 0 0 0 1 1 0 1 1 이면 0 0 에서 1 0 은 장애물이 없는데 장애물이 있는것으로 인식한다는 것이다...


    괜히 인접행렬 형태로 간소화해서 풀어보겠다고 했다가 틀렸다. 기하학 문제에선 여러가지 경우를 동시에 생각했어야 하는데 크으... 생각하지 못했다. 반성할 부분이다.


     
    #include<cstdio>
    
    using namespace std;
    
    struct obstacle{
    	int ax, ay;
    	int bx, by;
    };
    
    long long map[105][105];
    
    obstacle obs[105];
    
    int main(){
    	int n, m, k;
    	int a, b, c, d;
    
    	scanf("%d %d", &n, &m);
    
    
    	scanf("%d", &k);
    
    	for(int i=0; i<k; i++){
    		scanf("%d %d %d %d", &obs[i].ax, &obs[i].ay, &obs[i].bx, &obs[i].by);
    	}
    
    	map[0][0]=1;
    
    	for(int i=0; i<=n; i++)
    		for(int j=0; j<=m; j++){
    			bool up=true, left=true;
    			for(int piv=0; piv<k; piv++){
    
    				if(i>0){
    					if(i-1 == obs[piv].ax && j==obs[piv].ay && i==obs[piv].bx && j==obs[piv].by)
    						up=false;
    					if(i-1 == obs[piv].bx && j==obs[piv].by && i==obs[piv].ax && j==obs[piv].ay)
    						up=false;
    
    				}else
    					up=false;
    				if(j>0){
    					if(i == obs[piv].ax && j-1==obs[piv].ay && i==obs[piv].bx && j==obs[piv].by)
    						left=false;
    					if(i == obs[piv].bx && j-1==obs[piv].by && i==obs[piv].ax && j==obs[piv].ay)
    						left=false;
    				}
    				else
    					left=false;
    			}
    			if(up)
    				map[i][j] += map[i-1][j];
    			if(left)
    				map[i][j] += map[i][j-1];
    		}
    
    	printf("%lld\n",map[n][m]);
    
    	return 0;
    }
    

    '알고리즘 > acmicpc' 카테고리의 다른 글

    2229  (0) 2016.07.24
    4307  (0) 2015.10.17
    1577  (0) 2015.10.16
    1946  (0) 2015.10.16
    2590  (0) 2015.10.15
    1931  (0) 2015.10.14

    댓글 0

Designed by Tistory.