题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1411
题目大意：连连看，给出每次连线的两个坐标，求能消去多少方块，拐弯最多2次
Sample Input
3 4
1 1 2 2
3 3 4 4
2 2 1 1
6
1 1 1 2
1 3 1 4
2 1 2 2
2 3 2 4
3 1 3 2
3 3 3 4
0 0
Sample Output
12
分析：连线可以从外围绕过去，用BFS求出两个坐标能够到达的最少拐弯次数。注意是最少拐弯次数，而不是最短距离
这道题目坑死我了，倒不是因为它的算法难，是一些小知识点
代码如下：
# include<iostream>
# include<cstdio>
# include<cstring>
# include<queue>
using namespace std; int n,m;
int map[][];
bool vis[][];
int dx[]= {-,,,};
int dy[]= {,-,,};
struct node
{
int x,y,turn;
} st;
queue<node>q; bool BFS(int x1,int y1,int x2,int y2)
{
if(map[x1][y1]== || map[x2][y2]== ||map[x1][y1]!=map[x2][y2] ||x1==x2&&y1==y2)
return false;
st.x = x1;
st.y = y1;
while(!q.empty()) q.pop(); //坑死，while写成了if，半天没看出来
memset(vis,,sizeof(vis));
st.turn = -;
q.push(st);
while(!q.empty())
{
st = q.front();
q.pop(); node tmp;
for(int i=; i<; i++)
{
for(int j=;; j++)
{
tmp.x = st.x + j*dx[i];
tmp.y = st.y + j*dy[i];
tmp.turn = st.turn+;
if(tmp.x< || tmp.y< ||tmp.x>n+ ||tmp.y>m+) break;
if(map[tmp.x][tmp.y])
{
if(tmp.x==x2 && tmp.y==y2) return true;
break;
}
if(vis[tmp.x][tmp.y]) continue;
vis[tmp.x][tmp.y] = ;
if(tmp.turn<) //等于2的没必要加入队列了，他已经是叶子了
q.push(tmp);
}
}
}
return false;
} int main()
{
//freopen("in.txt","r",stdin);
int t,x1,y1,x2,y2;
while(scanf("%d%d",&n,&m) &&n &&m) //因为给出n、m为0结束，如果写不等于EOF会超时，错了好几次才反应过来
{
memset(map,,sizeof(map));
for(int i=; i<=n; i++)
for(int j=; j<=m; j++)
scanf("%d",&map[i][j]);
scanf("%d",&t);
int ans=;
while(t--)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(BFS(x1,y1,x2,y2))
{
ans += ;
map[x1][y1] = ;
map[x2][y2] = ;
}
}
printf("%d\n",ans);
}
return ;
}
还有另外一种思路，具体看代码：
#include "stdio.h"
int a[][];
int x1,y1,x2,y2;
int m,n;
int process()
{
int b[][];
int i,j;
int temp,pos;
for(i=;i<=n+;i++)
for(j=;j<=m+;j++)
b[i][j]=a[i][j];
if(b[x1][y1]!=b[x2][y2] || b[x1][y1]==) return ;
temp=;
while(x1+temp<=n+)
{
if(b[x1+temp][y1]==)
{
b[x1+temp][y1]=-;
temp++;
}
else if(x1+temp==x2 && y1==y2) return ;
else break;
}
temp=;
while(x1-temp>=)
{
if(b[x1-temp][y1]==)
{
b[x1-temp][y1]=-;
temp++;
}
else if(x1-temp==x2 && y1==y2) return ;
else break;
}
temp=;
while(y1+temp<=m+)
{
if(b[x1][y1+temp]==)
{
b[x1][y1+temp]=-;
temp++;
}
else if(x1==x2 && y1+temp==y2) return ;
else break;
}
temp=;
while(y1-temp>=)
{
if(b[x1][y1-temp]==)
{
b[x1][y1-temp]=-;
temp++;
}
else if(x1==x2 && y1-temp==y2) return ;
else break;
}
temp=;
while(x2+temp<=n+)
{
if(b[x2+temp][y2]==-) return ;
else if(b[x2+temp][y2]==)
{
b[x2+temp][y2]=-;
temp++;
}
else break;
}
temp=;
while(x2-temp>=)
{
if(b[x2-temp][y2]==-) return ;
else if(b[x2-temp][y2]==)
{
b[x2-temp][y2]=-;
temp++;
}
else break;
}
temp=;
while(y2+temp<=m+)
{
if(b[x2][y2+temp]==-) return ;
else if(b[x2][y2+temp]==)
{
b[x2][y2+temp]=-;
temp++;
}
else break;
}
temp=;
while(y2-temp>=)
{
if(b[x2][y2-temp]==-) return ;
else if(b[x2][y2-temp]==)
{
b[x2][y2-temp]=-;
temp++;
}
else break;
}
if(y2<y1)
{
temp=;
while(x2+temp<=n+ && b[x2+temp][y2]==-)
{
pos=;
while(y2+pos<=m+ && b[x2+temp][y2+pos]==)
pos++;
if(y2+pos<=m+ && b[x2+temp][y2+pos]==-) return ;
temp++;
}
temp=;
while(x2-temp>= && b[x2-temp][y2]==-)
{
pos=;
while(y2+pos<=m+ && b[x2-temp][y2+pos]==)
pos++;
if(y2+pos<=m+ && b[x2-temp][y2+pos]==-) return ;
temp++;
}
}
else if(y2>y1)
{
temp=;
while(x2+temp<=n+ && b[x2+temp][y2]==-)
{
pos=;
while(y2-pos>= && b[x2+temp][y2-pos]==)
pos++;
if(y2-pos>= && b[x2+temp][y2-pos]==-) return ;
temp++;
}
temp=;
while(x2-temp>= && b[x2-temp][y2]==-)
{
pos=;
while(y2-pos>= && b[x2-temp][y2-pos]==)
pos++;
if(y2-pos>= && b[x2-temp][y2-pos]==-) return ;
temp++;
}
}
if(x2<x1)
{
temp=;
while(y2+temp<=m+ && b[x2][y2+temp]==-)
{
pos=;
while(x2+pos<=n+ && b[x2+pos][y2+temp]==)
pos++;
if(x2+pos<=n+ && b[x2+pos][y2+temp]==-) return ;
temp++;
}
temp=;
while(y2-temp>= && b[x2][y2-temp]==-)
{
pos=;
while(x2+pos<=n+ && b[x2+pos][y2-temp]==)
pos++;
if(x2+pos<=n+ && b[x2+pos][y2-temp]==-) return ;
temp++;
}
}
else if(x2>x1)
{
temp=;
while(y2+temp<=m+ && b[x2][y2+temp]==-)
{
pos=;
while(x2-pos>= && b[x2-pos][y2+temp]==)
pos++;
if(x2-pos>= && b[x2-pos][y2+temp]==-) return ;
temp++;
}
temp=;
while(y2-temp>= && b[x2][y2-temp]==-)
{
pos=;
while(x2-pos>= && b[x2-pos][y2-temp]==)
pos++;
if(x2-pos>= && b[x2-pos][y2-temp]==-) return ;
temp++;
}
}
return ;
}
int main()
{
int step;
int i,j;
int num;
scanf("%d%d",&n,&m);
while(n!= || m!=)
{
num=;
for(i=;i<=n+;i++)
for(j=;j<=m+;j++)
a[i][j]=;
for(i=;i<=n;i++)
for(j=;j<=m;j++)
scanf("%d",&a[i][j]);
scanf("%d",&step);
for(i=;i<step;i++)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(process()==)
{
a[x1][y1]=;a[x2][y2]=;
num=num+;
}
}
printf("%d\n",num);
scanf("%d%d",&n,&m);
}
return ;
}