题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<queue>
#include <utility>
#define x first
#define y second
using namespace std;
const int N = 1010;
typedef pair<int,int> PII;
PII path[N][N];
int a[N][N];
int n;
bool Got[N][N];
void bfs()
{
    queue<PII>p;
    p.push({n-1,n-1});
    Got[n-1][n-1]=true;
     int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
   //int dx[] = {0,1,0,-1}, dy[] = {1,0,-1,0};
    while(p.size())
    {
      auto t = p.front();
      p.pop();
      for(int i = 0; i < 4 ; i ++ )
      {
          int x = t.x + dx[i];
          int y = t.y + dy[i];
          if(a[x][y]==1)continue;
          if(Got[x][y]==1)continue;
          if(x<0||x>n-1||y<0||y>n-1)continue;
          Got[x][y] = true;
          path[x][y] = t;
          p.push({x,y});
      }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i = 0; i < n; i ++ )
      for(int j = 0; j < n ; j ++ )
         scanf("%d",&a[i][j]);
  bfs();
  PII end;
  end.x = 0;
  end.y = 0;
  cout << 0 <<" " << 0 << endl;
  while(end.x!=n-1||end.y!=n-1)
  {
      int tx = path[end.x][end.y].x;
      int ty = path[end.x][end.y].y;
      end.x = tx;
      end.y = ty;
      cout << tx << " " << ty << endl;
  }
    return 0;
}