문제 C: 솔 로 몬 왕 의 보물

문제 C: 솔 로 몬 왕 의 보물
시간 제한: 1 Sec  메모리 제한: 128 MB 제출: 181  해결: 64 [제출] [상태] [토론 판] [명제 자: admin]
제목 설명
고대 전설 에 따 르 면 솔 로 몬 왕 은 지혜 의 대표 이자 부의 상징 이 었 다.그 는 강력 하고 부유 한 나 라 를 세 워 황금 상아 와 다이 아몬드 를 대량으로 모 았 고 이 값 진 보물 들 을 신비 로 운 곳 에 숨 겼 다. 이것 이 바로 세상 사람들 이 주목 하 는 '솔 로 몬 왕 의 보물' 이다.몇 세기 동안 사람들 은 이미 잃 어 버 린 고대 문명 의 보물 을 찾 아 황금 과 다이 아몬드 를 많이 생산 하 는 보 지 를 찾 아 왔 다.솔 로 몬 왕 의 보물 을 찾 던 모험 가 들 은 돌아 오지 않 았 고, 아직 까지 이 수수 께 끼 를 풀 사람 이 없 었 다.헨리 남작 은 행운 의 여행 에서 300 년 전 포르투갈 귀족 이 남 긴 양가죽 롤 에 적 힌 솔 로 몬 왕 의 보물 지도 와 보물 찾기 비적 을 얻 었 다.이 보물 지도 의 유혹 에 헨리 남작 은 존 대령 과 용감 한 사냥꾼 인 콰 트 만 을 초청 해 어두 운 땅 밑 에 묻 힌 솔 로 몬 왕 의 보물 을 찾 는 험난 한 과정 을 시작 했다.그들 은 끝 없 는 사막 과 짙 은 그늘 이 해 를 가 리 는 원시림 을 가로 질 러 거 센 격류 와 위험한 여울 을 넘 어 구름 속으로 우뚝 솟 은 준 령 설산 을 넘 어 사막의 무더위 와 얼음 과 눈 추 위 를 실컷 맛 보고 보물 지도 에서 아프리카 의 원시 적 인 신비 한 나라 쿠 안나 로 안내 했다.이곳 에는 잔혹 한 사람 이 순사 하 는 제도 가 있다. 천 명의 아내 가 있 는 외눈박이 폭군 트 왈 라 가 있 고 독수리 처럼 추악 하고 간사 하 며 늙어 죽지 않 는 소 서 러 가 고 르 도 있 으 며 아름 답 고 지혜 로 운 절세의 가인 플 라 타 도 있다.낯 설 고 위험한 땅 에서 보물 찾기 영웅 세 명 이 고생 끝 에 절세의 가인 플 라 타의 도움 으로 해저 깊 은 곳 에서 이 값 진 보물 을 간직 하고 있 는 거대 한 보물 동굴 을 찾 았 다.그러나 소 서 러 가 고 르 의 치밀 한 계획 으로 치 명 적 인 재난 이 다가 오고 있다.보물 동굴 의 동굴 문 은 매우 견고 하고 동굴 문 이 닫 혀 있 으 며 동굴 문 을 여 는 비밀 을 모 르 면 보물 동굴 의 동굴 문 을 열 수 없다.보물 동굴 의 동굴 한쪽 에 이상 한 사각형 암호 배열 이 있다.보물 찾기 비적 의 기록 에 따 르 면 암호 배열 각 줄 의 왼쪽 과 각 열의 맨 위 에 루비 버튼 이 있 습 니 다.모든 단 추 는 왼쪽으로 또는 오른쪽으로 돌 릴 수 있다.왼쪽으로 단 추 를 한 번 돌 릴 때마다 해당 줄 이나 열 에 있 는 숫자 가 1 증가 합 니 다.오른쪽으로 단 추 를 한 번 돌 릴 때마다 해당 줄 이나 열 에 있 는 숫자 는 1 로 줄어든다.직사각형 암호 배열 의 몇몇 특정 위치 에 에메랄드 가 박 혀 있다.모든 에메랄드 위치의 숫자 가 보물 지도 에 기 재 된 비밀번호 와 똑 같 을 때 닫 힌 동굴 문 은 자동 으로 천천히 열 린 다.소 서 러 가 고 르 는 문 을 여 는 비밀 을 알 고 있 었 다.보물 찾기 꾼 이 동굴 문 을 여 는 것 을 막 기 위해 소 서 러 가 고 르 는 문 을 여 는 암호 배열 에 0 의 초기 상 태 를 설정 했다.동굴 문 을 열 려 고 하 는 보물 찾기 자 는 단 추 를 빠르게 돌리 지 못 해 모든 에메랄드 위치의 숫자 가 보물 지도 에 기 재 된 비밀번호 와 똑 같 으 면 보물 동굴 의 현묘 한 암기 기관 이 자동 으로 작 동 해 보물 찾기 자가 멸망 공격 을 받 아 비명 에 죽는다.당신 은 세 명의 보물 찾기 영웅 이 보물 동굴 의 동굴 문 을 순조롭게 열 수 있 도록 도와 줄 수 있 습 니까?프로 그래 밍 작업: 주어진 암호 배열 에 대해 정확 한 암 호 를 얻 은 루비 단추 의 회전 순 서 를 찾 습 니 다.
 
입력
입력 한 첫 줄 에 정정 수 T (T ≤ 5) 가 T 조 데이터 가 있 음 을 나 타 냅 니 다.각 그룹의 데이터 의 첫 줄 에는 3 개의 정수 n, m 와 k 가 있 는데 동굴 암호 배열 은 모두 n 줄 과 m 열 이 있 음 을 나타 낸다.
 
출력
각 그룹의 데이터 에 대해 서 는 Yes 나 No 를 한 줄 로 출력 합 니 다.출력 Yes 는 정확 한 암 호 를 얻 은 루비 단추 의 회전 시퀀스 가 있 음 을 표시 합 니 다.출력 No 는 정확 한 암 호 를 얻 은 루비 단추 의 회전 순 서 를 찾 을 수 없 음 을 표시 합 니 다.
 
샘플 입력

2
2 2 4
1 1 0
1 2 0
2 1 2
2 2 2
2 2 4
1 1 0
1 2 0
2 1 2
2 2 1

 
샘플 출력

Yes
No

 
제시 하 다.
100% 의 데이터 에 대하 여 1 ≤ n, m, k ≤ 1000, k ≤ n×m，∣c∣≤1,000,000。
 
 
같은 업 종 을 고려 할 때, 차 이 는 열의 차이 이 고, 같은 열 은 같은 이치 이 며, 같은 열 은 같은 값 이 다 르 면 안 된다.
 

#include
#define ll long long
using namespace std;
int a[1005];
int b[1005];
int c[1005];
int mp[1005][1005];
int mm[1005][1005];
bool vis1[1005][1005];
bool vis2[1005][1005];
int main()
{
    int t,n,m,k;
    scanf("%d",&t);

    while(t--)
    {
        memset(vis1,0,sizeof(vis1));
        memset(vis2,0,sizeof(vis2));
        memset(mp,0,sizeof(mp));
        memset(mm,0,sizeof(mm));
        scanf("%d%d%d",&n,&m,&k);

        for(int i=0;ia[j]?1:(mp[a[j]][a[i]]=-mp[a[j]][a[i]],mp[a[i]][a[j]]=-mp[a[i]][a[j]]);
                        vis1[a[i]][a[j]]=vis1[a[j]][a[i]]=1;
                    }
                    else if(abs(c[i]-c[j])!=abs(mp[a[i]][a[j]]))
                    {
                        flag = 1;
                        break;
                    }
                }
                if(a[i]==a[j])
                {
                    if(!vis2[b[i]][b[j]])
                    {
                        mm[b[i]][b[j]]=c[i]-c[j];
                        mm[b[j]][b[i]]=c[j]-c[i];
                        b[i]>b[j]?1:(mm[b[i]][b[j]]=-mm[b[i]][b[j]],mm[b[j]][b[i]]=-mm[b[j]][b[i]]);
                        vis2[b[i]][b[j]]=vis2[b[j]][b[i]]=1;
                    }
                    else if(abs(c[i]-c[j])!=abs(mm[b[i]][b[j]]))
                    {
                        flag = 1;
                        break;
                    }
                }
            }
            if(flag)
                break;
        }
        if(!flag) printf("Yes
");
        else printf("No
");
    }

    return 0;
}