1577

알고리즘/acmicpc 2015. 10. 16. 22:17 Posted by 아는 개발자

아 도로문제 ㅠㅠ

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


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

내 실수는 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;
}
728x90

'알고리즘 > 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