기 중 합숙 훈련 2020.01.14 [NOIP 보급 팀] 모 의 경기 C 팀 의 정리 - 샤 오 밍 의 게임

기 중 합숙 훈련 2020.01.14 [NOIP 보급 팀] 모 의 경기 C 팀 의 정리 - 샤 오 밍 의 게임
3. 샤 오 밍 의 게임 은 해 보 자 는 마음으로 이 문 제 를 풀 었 습 니 다. 당 황 스 럽 게 문 제 를 보 았 습 니 다. B 조 와 문 제 를 부 딪 쳤 습 니 다. 당 황 스 럽 고 시간 도 많 지 않 습 니 다. 폭력 을 행사 하 세 요. 40 점 만 받 으 면 됩 니 다.폭력 0 점 말 하지 마!그리고 정 해 를 완벽 하 게 피하 고 완벽 한 TLE 를 완벽 하 게 썼 습 니 다!
-- -- -- 화려 한 분할 선 -- --
본론 으로 돌아가다
3. 샤 오 밍 의 게임
제목: 샤 오 밍 은 요즘 게임 하 나 를 좋아한다.n * m 의 바둑판 을 지정 합 니 다. 위 에 두 개의 격자 가 있 습 니 다.게임 의 규칙 은 매우 간단 하 다. 시작 위치 와 목표 위 치 를 정 하고 샤 오 밍 은 한 걸음 한 걸음 위로, 아래, 왼쪽, 오른쪽 네 방향 으로 한 칸 을 이동 할 수 있다.같은 유형의 칸 으로 이동 하면 비용 은 0 이 고 그렇지 않 으 면 비용 은 1 이다.시작 위치 에서 목표 위치 로 이동 하 는 최소 비용 을 프로 그래 밍 하 십시오.Input 입력 파일 에는 여러 그룹의 데이터 가 있 습 니 다.첫 번 째 줄 에 두 개의 정수 n, m 를 포함 하고 바둑판 의 줄 수 와 열 수 를 표시 합 니 다.다음 n 줄 을 입력 하 십시오. 줄 마다 m 개의 칸 이 있 습 니 다 (\ # 또는 @ 표시 사용).다음 줄 에 네 개의 정수 x1, y1, x2, y2 를 입력 하 십시오. 각각 시작 위치 와 목표 위치 입 니 다.n, m 를 모두 0 으로 입력 하면 입력 이 끝 났 음 을 표시 합 니 다.출력 은 각 그룹의 데이터 에 대해 출력 이 시작 위치 에서 목표 위치 까지 최소 화 됩 니 다.각 그룹의 데이터 가 한 줄 을 독점 하 다.Sample Input 2 2 @# #@ 0 0 1 1 2 2 @@ @# 0 1 1 0 0 0 Sample Output 2 0
이 문 제 는 결코 가장 짧 은 길 등 고급 알고리즘 이나 어떤 고급 최적화 도 넣 을 수 없 는 것 이 아니다.근 데 사실은 기억 화 된 검색 문 제 잖 아!신 (심) 청 (태) 기 (붕) 상 (궤)!!!!!!100 점 이 야!60 점 드 렸 습 니 다!분석: 사실 이 문 제 는 경 계 를 보 는 것 이다. 자 모 를 바 꾸 지 않 으 면 자 모 를 바 꾸 지 않 고 비용 을 구 하 는 것 이지 가장 짧 은 거 리 를 구 하 는 것 이 아니다.넓 은 검색 을 통 해 기억 화 를 한 다음 에 배열 을 크게 열 어 AC 도 할 수 있 고 시간 도 초과 하지 않 을 정도 로 하면 됩 니 다!핵심 시험 점 은 뜻밖에도 - - - - 공간 을 누 르 는 것 이다!WHAT!
Pascal AC 코드 첨부:

uses math;
var
        n,m,i,j,x1,x2,y1,y2,minn:longint;
        map:array[0..1005,0..1005] of char;
        fx:array[1..4] of longint=(-1,0,1,0);
        fy:array[1..4] of longint=(0,-1,0,1);
        f:array[0..1005,0..1005] of longint;
        a:array[0..5000005,1..2] of longint;
procedure bfs(x,y:longint);
var
        head,tail,xx,yy:longint;
begin
        head:=0;
        tail:=1;
        a[tail,1]:=x;
        a[tail,2]:=y;
        while head<tail do
        begin
                inc(head);
                for i:=1 to 4 do
                begin
                        xx:=a[head,1]+fx[i];
                        yy:=a[head,2]+fy[i];
                        if (xx>=0) and (yy>=0) and (xx<n) and (yy<m) then
                        begin
                                if map[xx,yy]=map[a[head,1],a[head,2]] then
                                begin
                                        if f[a[head,1],a[head,2]]<f[xx,yy] then
                                        begin
                                                inc(tail);
                                                a[tail,1]:=xx;
                                                a[tail,2]:=yy;
                                                f[xx,yy]:=f[a[head,1],a[head,2]];
                                        end;
                                end
                                else
                                begin
                                        if f[a[head,1],a[head,2]]+1<f[xx,yy] then
                                        begin
                                                inc(tail);
                                                a[tail,1]:=xx;
                                                a[tail,2]:=yy;
                                                f[xx,yy]:=f[a[head,1],a[head,2]]+1;
                                        end;

                                end;
                        end;
                end;
        end;
        writeln(f[x2,y2]);
end;
begin
        readln(n,m);
        while (n<>0) or (m<>0) do
        begin
                for i:=0 to n-1 do
                begin
                        for j:=0 to m-1 do
                        begin
                                read(map[i,j]);
                                f[i,j]:=maxlongint div 2;
                        end;
                        readln;
                end;
                readln(x1,y1,x2,y2);
                f[x1,y1]:=0;
                bfs(x1,y1);
                readln(n,m);
        end;
end.

C + + AC 코드 첨부:

#include
#define inf 2100000000
using namespace std;
char map[505][505];
int f[505][505],a[5000005][3];
int ans,n,m,sx,sy,ex,ey,head,tail,x,y,xx,yy;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int main()
{
	scanf("%d%d",&n,&m);
	while (n!=0||m!=0)
	{
		for (int i=0;i<n;i++){
			for (int j=0;j<m;j++){
				map[i][j]=getchar();
				while (map[i][j]!='#'&&map[i][j]!='@') map[i][j]=getchar();
				f[i][j]=inf;
			}
		}
		scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
		head=0;
		tail=1;
		a[1][1]=sx;
		a[1][2]=sy;
		a[1][0]=0;
		ans=inf;
		while (head<tail)
		{
			head++;
			xx=a[head][1];
			yy=a[head][2];
			if (a[head][0]>ans)
				continue;
			for (int i=0;i<4;i++)
			{
				x=xx+dx[i];
				y=yy+dy[i];
				if (x>=0&&x<n&&y>=0&&y<m)
				{
					if (map[xx][yy]!=map[x][y]&&a[head][0]+1>=f[x][y]||map[xx][yy]==map[x][y]&&a[head][0]>=f[x][y]) continue;
					if (map[xx][yy]==map[x][y])
						a[++tail][0]=a[head][0];
					else
						a[++tail][0]=a[head][0]+1;
					if (a[tail][0]<f[x][y])
					f[x][y]=a[tail][0];
					a[tail][1]=x;
					a[tail][2]=y;
					if(x==ex&&y==ey)
						if (ans>a[tail][0])
							ans=a[tail][0];
				}
			}
		}
		printf("%d
",ans);
		scanf("%d%d",&n,&m);
	}
	return 0;
}

END！(거 친 녀석 들 의 관람 에 감 사 드 립 니 다)
기 중 합숙 훈련 2020.01.14 [NOIP 보급 팀] 시 뮬 레이 션 C 팀 총괄 (완)