acmicpc.net 7562(BFS), 3055(BFS), 7576,7569(BFS)

https://www.acmicpc.net/problem/7562

#include <cstdio>
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
    
int t,n,c[2],m[2];
int _y[]={-2,-1,1,2,2,1,-1,-2};
int _x[]={1,2,2,1,-1,-2,-2,-1};

int bfs(int c[2],int m[2])
{
	int visited[300][300]={0,};
	queue<vector<int>> q;
	vector<int> t;
	t.push_back(c[0]);
	t.push_back(c[1]);
	t.push_back(0);
	q.push(t);
	while(!q.empty())
	{
		vector<int> p = q.front();
		q.pop();
		if(p[0]==m[0] && p[1]==m[1])
			return p[2];
		for(int i=0;i<8;i++)
		{
			int ty = _y[i]+p[0];
			int tx = _x[i]+p[1];
			if(ty>n-1 || tx>n-1 || tx<0 || ty<0)
				continue;
			if(visited[ty][tx]==0)
			{
				vector<int> t;
				t.push_back(ty);
				t.push_back(tx);
				t.push_back(p[2]+1);
				q.push(t);
				visited[ty][tx] = 1;
			}
		}

	}
}

int main()
{
	scanf("%d",&t);
	for(int i=0;i<t;i++)
	{
		scanf("%d %d %d %d %d",&n,&c[0],&c[1],&m[0],&m[1]);
		printf("%d\n",bfs(c,m));
	}
    return 0;
}

https://www.acmicpc.net/problem/3055

# -*- encoding: cp949 -*-
import Queue
import copy
def bfs(y,x,maps,water):
    visited = [[0 for j in xrange(c)] for i in xrange(r)]
    q = Queue.Queue()
    q.put([y,x,copy.deepcopy(maps),0]) 
    visited[y][x] = 1
    while not q.empty():
        p = q.get()
        #print '\n'.join(map(lambda x:''.join(x),p[2]))
        #print
        if maps[p[0]][p[1]]=='D':
            return p[3]

        new_map = copy.deepcopy(p[2])
        for _r in xrange(r):
            for _c in xrange(c):
                if p[2][_r][_c]=='*':
                    for i in xrange(4):
                        wy,wx = _r+[1,0,-1,0][i],_c+[0,-1,0,1][i]
                        if wy>r-1 or wx>c-1 or wy<0 or wx<0:
                            continue
                        if p[2][wy][wx]=='.':
                            new_map[wy][wx] = '*'

        for i in xrange(4):
            ty,tx = p[0]+[1,0,-1,0][i],p[1]+[0,-1,0,1][i]
            if ty>r-1 or tx>c-1 or ty<0 or tx<0 or new_map[2] in ['*','X']:
                continue
            if visited[ty][tx]==0 and new_map[ty][tx] in ['.','D']:
                new_map[p[0]][p[1]] = '.'
                new_map[ty][tx] = 'S'

                q.put([ty,tx,copy.deepcopy(new_map),p[3]+1])

                visited[ty][tx] = 1
                new_map[p[0]][p[1]] = 'S'
                new_map[ty][tx] = '.'
    return 'KAKTUS'

r,c=map(int,raw_input().split())
arr = [list(raw_input()) for i in xrange(r)]
water = []
for i in xrange(r):
    for j in xrange(c):
        if arr[i][j]=='S':
            chr=[i,j]
        elif arr[i][j]=='*':
            water.append([i,j])
print bfs(chr[0],chr[1],arr,water)

https://www.acmicpc.net/problem/7576

https://www.acmicpc.net/problem/7569

7576은 7569번을 2차원으로 바꾸면 되기에 소스코드는 안올림. 이문제 풀면서 미세한 속도차를 발견했다.

Queue라이브러리를 사용하면 시간초과가 난다. 근데 이걸 그냥 리스트로 바꾸기만 했는데 시간초과가 

없어졌다. 큐가 더 빠를줄알았는데, 그냥 리스트로 하는게 더빠른지 몰랐다.

큐로 구현했을때는 아래 소스코드에서 q.append대신 q = Queue.Queue(); q.put()으로 집어넣고,

주석처리된 while not q.empty():부분을 해제시키고 그런식으로 변경해보면 된다.

# -*- encoding: cp949 -*-
import Queue
import sys
m,n,h = map(int,sys.stdin.readline().split())#map(int,raw_input().split())
arr = [[map(int,sys.stdin.readline().split()) for i in xrange(n)] for j in xrange(h)]
q = []
for i in xrange(h):
    for j in xrange(n):
        for k in xrange(m):
            if arr[i][j][k]==1:
                q.append([i,j,k,0])

answer = 0
for p in q:#while not q.empty():
    #p = q.get()
    for i in xrange(6):
        tz,ty,tx = p[0]+[0,0,0,0,1,-1][i],p[1]+[1,0,-1,0,0,0][i],p[2]+[0,-1,0,1,0,0][i]
        if tz>h-1 or ty>n-1 or tx>m-1 or tz<0 or ty<0 or tx<0:
            continue
        if arr[tz][ty][tx]==0:
            q.append([tz,ty,tx,p[3]+1])
            answer = max(p[3]+1, answer)
            arr[tz][ty][tx] = answer
 
flag = False
for i in xrange(h):
    for j in xrange(n):
        for k in xrange(m):
            if arr[i][j][k]==0:
                print -1
                flag = True
                break
        if flag: break
    if flag: break
if not flag:
    print answer